Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Диаметром кластера назовём максимальное расстояние между двумя точками в кластере. Для каждого кластера гарантируется, что диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x1; y1) и B(x2; y2) вычисляется по формуле: $d левая круглая скобка A; B правая круглая скобка = корень из: начало аргумента: левая круглая скобка x_2 минус x_1 правая круглая скобка в квадрате плюс левая круглая скобка y_2 минус y_1 правая круглая скобка в квадрате конец аргумента$ В файле А хранятся данные о звёздах двух кластеров, где H = 3, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична файлу А. Файл А Файл Б Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно. Для файла А найдите пары точек, которые образуют диаметр каждого кластера. Затем вычислите два числа: Px — минимальную из сумм абсцисс этих точек для всех кластеров и Py — минимальную из сумм ординат этих точек для всех кластеров. Для файла Б найдите два числа: Q1 — диаметр кластера с минимальным количеством точек и Q2 — максимальное расстояние от точки, образующей диаметр одного кластера, до точки, образующей диаметр другого кластера. Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке — сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000. Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла. [рис.] Ответ:
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Диаметром кластера назовём максимальное расстояние между двумя точками в кластере. Для каждого кластера гарантируется, что диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x1; y1) и B(x2; y2) вычисляется по формуле: $d левая круглая скобка A; B правая круглая скобка = корень из: начало аргумента: левая круглая скобка x_2 минус x_1 правая круглая скобка в квадрате плюс левая круглая скобка y_2 минус y_1 правая круглая скобка в квадрате конец аргумента$ В файле А хранятся данные о звёздах двух кластеров, где H = 3, W = 4 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична файлу А. Файл А Файл Б Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно. Для файла А найдите пары точек, которые образуют диаметр каждого кластера. Затем вычислите два числа: Px — минимальную из сумм абсцисс этих точек для всех кластеров и Py — минимальную из сумм ординат этих точек для всех кластеров. Для файла Б найдите два числа: Q1 — диаметр кластера с минимальным количеством точек и Q2 — максимальное расстояние от точки, образующей диаметр одного кластера, до точки, образующей диаметр другого кластера. Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке — сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке — сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000. Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла. [рис.] Ответ:
