Продолжим разбирать региональный этап Всероссийской олимпиады школьников по информатике 2009 года второй задаче первого тура. Читаем условие:
Если бы ограничения в задаче были поменьше можно было бы проверить все целочисленные точки прямоугольника на принадлежность кругу с помощью теоремы Пифагора (а именно, что расстояние от точки до центра круга не превышает радиуса круга).
Однако можно заметить, что в каждом столбце кругу принадлежит непрерывная последовательность точек. И если найти верхнюю (u) и нижнюю (l) её границу, то можно не проверять точки посередине, а прибавить к ответу u - l + 1 (плюс 1, так как обе границы включительно).
Этих рассуждений уже достаточно, чтобы начать писать решение. Считаем данные и заведём переменную, в которую будем накапливать ответ:
Модуль math подключил, так как нам придётся воспользоваться теоремой Пифагора и вычислять квадратный корень.
Теперь можно пройти по каждой координате x (столбцу), в которых встречаются и прямоугольник, и круг. Для этого сделаем проекции прямоугольника и круга на ось Ox, получим отрезки [x1, x2] и [x - r, x + r]. Чтобы найти их пересечение достаточно взять правую точку из левых концов отрезков и левую - из правых:
Теперь такой же трюк (пересечение отрезков) нужно выполнить для фиксированного столбца i. Для прямоугольника снова всё просто: [y1, y2].
Для круга проведём вертикальную хорду. Заметим, что можно найти её половину p как катет прямоугольного треугольника. И тогда верхнюю и нижнюю границы находим прибавлением и вычитанием p из y.
В коде я не стал выделять это в отдельный шаг и сразу нахожу границы для пересечения прямоугольника и круга:
Теперь к ответу прибавляем их разницу, но надо следить за тем, чтобы она не была отрицательной (такое возможно, когда в текущем столбце прямоугольник и круг не имею общих точек):
Осталось вывести результат:
Получилась довольно приятная задача на геометрию без всяких подводных камней и частных случаев.
Предыдущий выпуск: Задача 530. Чёрно-белая графика
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
