Московская городская олимпиада школьников по информатике,
2003/04 учебный год
при поддержке компаний
Задача I. Дремучий лес - 2
| Имя входного файла: | i.in |
| Имя выходного файла: | i.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Требуется определить, кажется ли лес дремучим данному наблюдателю.
На карте леса все деревья изображаются кругами. При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются), также одно дерево может находиться внутри другого. Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев.
Формат входных данных
Во входном файле содержится сначала целое число N - количество деревьев (1≤N≤50000). Затем идут два числа, задающих координаты наблюдателя. Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье - радиус. Все координаты задаются точно, и выражаются вещественными числами не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 100000.Формат выходных данных
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.
Примеры
| i.in | i.out |
4 0 0 2 2 2 -2 2 2 -2 -2 2 2 -2 2 |
YES |
2 10 10 0 0 1 0.5 0 2 |
NO 100.000 100.000 |