Олимпиадная задача: раскрасьте точки
Содержимое статьи:
На плоскости покрашены в черный цвет точки с целыми координатами (x,y), где x,y принимают целые значения от 1 до 2024. Всего имеется 20242 таких точек. Ваша задача — перекрасить некоторые из этих точек в красный цвет при условии, что каждый отрезок, концы которого окрашены в красный, содержит по крайней мере одну чёрную точку. Необходимо найти максимальное число точек, которое можно перекрасить в красный.
Советы:
- Используйте свойство, что для определения черного цвета точки достаточно проверить ее координаты.
- Попробуйте использовать рекурсивный подход или динамическое программирование.
- Подумайте о разбиении плоскости на квадраты или прямоугольники для упрощения задачи.
Комментарии