Датчики передают измерения приёмнику. В идеализированной модели без препятствий приёмник принимает сигнал от датчика, если расстояние между ними не больше radius. Граница зоны приёма включена.
Приёмник можно поставить в любую точку с целыми координатами (x, y) внутри квадрата −limit ≤ x ≤ limit, −limit ≤ y ≤ limit.
Выберите положение по следующим правилам, применяемым последовательно:
- Принять сигнал от наибольшего числа датчиков.
- При равном количестве выбрать положение ближе к началу координат.
- При равном расстоянии выбрать меньший x.
- Если и x равны, выбрать меньший y.
Что сделать
squared_distance(x1, y1, x2, y2) возвращает квадрат расстояния между двумя точками.covered_count(x, y, points, r) возвращает число датчиков в зоне приёмника и использует squared_distance. Список points содержит пары координат датчиков.best_position(points, r, limit) возвращает выбранную пару (x, y). При поиске используйте covered_count и squared_distance.
Реализуйте эти функции, затем считайте координаты датчиков, вызовите функции и выведите ответ. Функции ничего не считывают и не печатают. Датчики с одинаковыми координатами считаются разными устройствами: учитывайте каждый.
Квадрат расстояния равен (x2 − x1)² + (y2 − y1)². Для проверки зоны и сравнения расстояний извлекать квадратный корень не требуется.
Входные данные
Первая строка: целые числа n limit radius, где 1 ≤ n ≤ 30, 0 ≤ limit ≤ 15, 0 ≤ radius ≤ 40. Следующие n строк содержат целые координаты датчиков x y, каждая от −30 до 30. Все координаты и радиус измерены в одинаковых единицах.
Выходные данные
Три целых числа через пробел: выбранные координаты x y и количество доступных из этой точки датчиков.
| № | Входные данные | Выходные данные |
|
1
|
3 2 1
-1 0
1 0
0 1
|
0 0 3
|
|
2
|
2 1 0
-1 0
1 0
|
-1 0 1
|