Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Отрезок и окружности

(Время: 1 сек. Память: 16 Мб Сложность: 58%)

Для начала рассмотрим более простую задачу. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до центра координат возрастает. Для такого отрезка ответ очевиден – это количество целых чисел между расстояниями от центра координат до обоих концов отрезка.

Теперь необходимо свести данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом, исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к (0; 0) точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее.


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483