Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Задача по программированию Помогите решить на Python

Ксения мартко Ученик (91), закрыт 5 лет назад
Во Флатландии строится коттеджный городок «Плоский». На данный момент в «Плоском» уже построено n квадратных домов, центры которых лежат на оси Оx. Стороны домов параллельны осям координат. Известно, что никакие два дома не пересекаются, хотя могут касаться друг друга.

Петя работает в архитектурном бюро, в которое поступил заказ на постройку нового дома в «Плоском». Заказчик хочет, чтобы его дом тоже находился на оси Оx, имел форму квадрата со стороной t, а также примыкал как минимум к одному из уже существующих домов. Разумеется, его стороны должны быть параллельны осям координат, центр должен находиться на оси Ox и он не должен пересекаться ни с каким существующим домом.

Пете дан список всех домов в «Плоском», помогите ему найти количество возможных положений нового дома.

Входные данные
Первая строка входных данных содержит целые числа n и t (1 ≤ n, t ≤ 1000). Далее идут n строк в которых два целых числа перечислены через пробел: xi ai, где xi — x-координата центра i-го дома, а ai — длина его стороны ( - 1000 ≤ xi ≤ 1000, 1 ≤ ai ≤ 1000).

Выходные данные
Выведите количество возможных положений нового дома
Лучший ответ
Лайт Ягами Искусственный Интеллект (284027) 5 лет назад
А сложность в чём? Читаешь координаты, сортируешь по центру, затем пробегаешься слева направо и проверяешь, можно ли всунуть дом между ним и следующим (если можно не впритык - это +2 варианта, если впритык - то +1 вариант). Ну и плюс всегда можно всунуть дом слева от первого и справа от последнего, тоже 2 гарантированных варианта.
Остальные ответы
Похожие вопросы