|
Отрезок и окружности
(Время: 1 сек. Память: 16 Мб Сложность: 58%)
Для начала рассмотрим более простую задачу. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до центра координат возрастает. Для такого отрезка ответ очевиден – это количество целых чисел между расстояниями от центра координат до обоих концов отрезка.
Теперь необходимо свести данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом, исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к (0; 0) точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.
Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее.
| |
