Задание 27 ЕГЭ по информатике

Ведущие агрономы компании «Царство кленового сиропа» изучают качество земли в большом кленовом саду. Перед ними стоит задача – проанализировать различные участки сада и сделать выводы о наиболее плодородных местах для дальнейшей посадки новых деревьев, что позволит возрастить объемы производства кленового сиропа.

По итогам сбора информации имеется отчёт – набор данных, включающий записи о позициях в саду, отмеченных агрономами. Каждая позиция характеризуется двумя вещественными координатами, отражающими ее положение в декартовой системе координат. Специалисты включили в отчет позиции двух видов: плодородные и неплодородные.

Чтобы минимизировать количество неприжившихся саженцев кленовых деревьев, решено, что нельзя сажать новые деревья в областях, близлежащих к неплодородным позициям. Такие запретные области определяются как окружности с радиусом $R_1 = 5$, центрами которых являются неплодородные позиции. В конце концов необходимо выделить области, подходящие для посадки, которые характеризуются как окружности с радиусом $R_2 = 7$ с центрами, которые определяются ранее выделенными плодородными позициями. Среди таких областей нужно найти оптимальную: такую, внутри которой находится наибольшее количество плодородных позиций (разумеется, находящихся вне запретных областей). А если оптимальных областей несколько, выбрать область с наибольшей суммой координат.

В файле A в первой строке записаны числа $N$ и $K$. В остальных строках хранятся записи о координатах позиций. Первые $N$ строк содержат координаты (два вещественных числа) плодородных позиций, остальные $K$ – неплодородных. Известно, что количество записей не превышает 1100.

Структура хранения информации о товарах в файле В аналогична файлу А, а количество записей не превышает 11000.

Для каждого файла определите координаты центров оптимальной области.

В ответе запишите четыре числа: в первой строке сначала значение произведения первой координаты на $10^{9}$, затем значение произведения второй координаты на $10^{9}$, для файла А, во второй строке – аналогичные данные для файла В.

Примечание. Метрикой расстояния между двумя позициями $A(x_1, y_1)$ и $B(x_2, y_2)$ является формула Евклида:

$d(A,B) = \sqrt{(x_2−x_1)^2+(y_2−y_1)^2}$.

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20615_27A.txt

Файл В к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20615_27B.txt