Задача №113516. Парк
В столице города Бестеланд есть огороженный парк, площадь которого представляет собой прямоугольник. Деревья и посетители в парке представляют собой круги. В парке есть четыре входа, по одному в каждом углу (1 = внизу слева, 2 = внизу справа, 3 = верхний правый, 4 = верхний левый). Посетители могут войти и выйти из парка только через входы. Посетители могут войти и выйти из парка, когда они касаются обеих сторон угла соответствующего входа. Посетители могут свободно передвигаться по парку, но они не могут пересекаться ни с деревьями, ни с забором. Ваша задача для каждого посетителя, учитывая вход, через который он войдет в парк, рассчитать через какие входы он может выйти из парка.
Первая строка ввода содержит два целых числа n и m : число деревьев в парке и количество посетителей. Вторая строка ввода содержит два целых числа w и h : ширину и высоту парковой зоны. Левый нижний угол имеет координаты(0, 0), верхний правый угол имеет координаты ( w , h ) . следующие строки описывают деревья. Каждая строка содержит три целых числа x , y и r : координаты центра дерева ( x , y ) и его радиус r . Деревья не перекрывают друг друга или забор. Наконец, есть m строк, которые описывают посетителей. Каждая строка содержит два целых числа r и e: радиус посетителя, и вход, который они войдут в парк. Кроме того, ни одно дерево не перекрывает квадратную площадь в каждом углу, где находится радиус наибольшего посетителя.
Вы должны вывести для каждого посетителя одну строку, содержащую входы, через которые посетитель может выйти из парка, в отсортированном порядке без пробелов между ними.
Два объекта касаются, если они имеют одну общую точку. Два объекта перекрываются, если они имеют более одной общей точки
4 k < w , h < 10 9 где k - радиус самого большого дерева
подзадача 1(27 баллов)
1 < = n < = 2000
m = 1
подзадача 2(31 балл)
1 < = n < = 200
1 < = m < = 10 5
подзадача 3(42 балл)
1 < = n < = 2000
1 < = m < = 10 5
5 3 16 11 11 8 1 6 10 1 7 3 2 10 4 1 15 5 1 1 1 2 2 2 1
1234 2 14