27012.py
ФИПИ: Задание 27. Анализ данных. Кластеризация
Фрагмент звёздного неба спроецирован на плоскость
с декартовой системой координат.
Учёный решил провести кластеризацию полученных точек,
являющихся изображениями звёзд, то есть разбить их множество
на N непересекающихся непустых подмножеств (кластеров),
таких что точки каждого подмножества лежат внутри
прямоугольника со сторонами длиной H и W, причём
эти прямоугольники между собой не пересекаются.
Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует
и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку в нём,
сумма расстояний от которой до всех остальных
точек кластера минимальна.
У каждого кластера есть гарантированно единственный центр.
Расстояние между двумя точками на плоскости
A(x1,y1) и B(x2,y2) вычисляется по формуле:
d(A,B) = sqrt((x2−x1)^2 + (y2−y1)^2)
В файле A хранятся данные о звёздах двух кластеров,
где H=6, W=4.5 для каждого кластера.
В каждой строке записана информация
о расположении на карте одной звезды:
сначала координата x, затем координата y.
Значения даны в условных единицах.
Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров,
где H=6, W=5 для каждого кластера.
Известно, что количество звёзд не превышает 1000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек,
являющихся аномалиями, возникшими в результате помех при передаче данных.
Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера,
затем найдите два числа:
Px — сумму абсцисс центров кластеров,
Py — сумму ординат центров кластеров.
Для файла Б найдите два числа:
Q1 — минимальное расстояние между точками,
принадлежащими двум различным кластерам,
Q2 — максимальное расстояние между точками,
принадлежащими двум различным кластерам.
В ответе запишите четыре числа:
в первой строке — сначала абсолютную
величину целой части произведения Px×10000,
затем абсолютную величину целой части произведения Py×10000;
во второй строке — сначала целую часть произведения Q1×10000,
затем целую часть произведения Q2×10000.
"""
ФИПИ: Задание 27. Анализ данных. Кластеризация
Фрагмент звёздного неба спроецирован на плоскость
с декартовой системой координат.
Учёный решил провести кластеризацию полученных точек,
являющихся изображениями звёзд, то есть разбить их множество
на N непересекающихся непустых подмножеств (кластеров),
таких что точки каждого подмножества лежат внутри
прямоугольника со сторонами длиной H и W, причём
эти прямоугольники между собой не пересекаются.
Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует
и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку в нём,
сумма расстояний от которой до всех остальных
точек кластера минимальна.
У каждого кластера есть гарантированно единственный центр.
Расстояние между двумя точками на плоскости
A(x1,y1) и B(x2,y2) вычисляется по формуле:
d(A,B) = sqrt((x2−x1)^2 + (y2−y1)^2)
В файле A хранятся данные о звёздах двух кластеров,
где H=6, W=4.5 для каждого кластера.
В каждой строке записана информация
о расположении на карте одной звезды:
сначала координата x, затем координата y.
Значения даны в условных единицах.
Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров,
где H=6, W=5 для каждого кластера.
Известно, что количество звёзд не превышает 1000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек,
являющихся аномалиями, возникшими в результате помех при передаче данных.
Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера,
затем найдите два числа:
Px — сумму абсцисс центров кластеров,
Py — сумму ординат центров кластеров.
Для файла Б найдите два числа:
Q1 — минимальное расстояние между точками,
принадлежащими двум различным кластерам,
Q2 — максимальное расстояние между точками,
принадлежащими двум различным кластерам.
В ответе запишите четыре числа:
в первой строке — сначала абсолютную
величину целой части произведения Px×10000,
затем абсолютную величину целой части произведения Py×10000;
во второй строке — сначала целую часть произведения Q1×10000,
затем целую часть произведения Q2×10000.
"""
третий метод решения задачи 27, DBSCAN"""
ФИПИ: Задание 27. Анализ данных. Кластеризация
Фрагмент звёздного неба спроецирован на плоскость
с декартовой системой координат.
Учёный решил провести кластеризацию полученных точек,
являющихся изображениями звёзд, то есть разбить их множество
на N непересекающихся непустых подмножеств (кластеров),
таких что точки каждого подмножества лежат внутри
прямоугольника со сторонами длиной H и W, причём
эти прямоугольники между собой не пересекаются.
Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует
и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку в нём,
сумма расстояний от которой до всех остальных
точек кластера минимальна.
У каждого кластера есть гарантированно единственный центр.
Расстояние между двумя точками на плоскости
A(x1,y1) и B(x2,y2) вычисляется по формуле:
d(A,B) = sqrt((x2−x1)^2 + (y2−y1)^2)
В файле A хранятся данные о звёздах двух кластеров,
где H=6, W=4.5 для каждого кластера.
В каждой строке записана информация
о расположении на карте одной звезды:
сначала координата x, затем координата y.
Значения даны в условных единицах.
Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров,
где H=6, W=5 для каждого кластера.
Известно, что количество звёзд не превышает 1000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек,
являющихся аномалиями, возникшими в результате помех при передаче данных.
Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера,
затем найдите два числа:
Px — сумму абсцисс центров кластеров,
Py — сумму ординат центров кластеров.
Для файла Б найдите два числа:
Q1 — минимальное расстояние между точками,
принадлежащими двум различным кластерам,
Q2 — максимальное расстояние между точками,
принадлежащими двум различным кластерам.
В ответе запишите четыре числа:
в первой строке — сначала абсолютную
величину целой части произведения Px×10000,
затем абсолютную величину целой части произведения Py×10000;
во второй строке — сначала целую часть произведения Q1×10000,
затем целую часть произведения Q2×10000.
"""
третий метод решения задачи 27, DBSCAN