РЕШУ ЕГЭ — информатика

Задания

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд  — это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид,  — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A левая круглая скобка x_1, y_1 правая круглая скобка$ и $B левая круглая скобка x_2, y_2 правая круглая скобка$ вычисляется по формуле: $d левая круглая скобка A, B правая круглая скобка = корень из: начало аргумента: левая круглая скобка x_1 минус x_2 правая круглая скобка в квадрате плюс левая круглая скобка y_1 минус y_2 правая круглая скобка в квадрате конец аргумента .$

Даны два входных файла (файл 27A и файл 27Б). В файле 27A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле 27Б хранятся данные о звёздах трёх кластеров.

Файл 27А.txt

Файл 27Б.txt

Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле 27Б аналогична файлу 27А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: P_x  — среднее арифметическое абсцисс центров кластеров, и P_y  — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения P_x × 10 000, затем целую часть произведения P_y × 10 000 для файла 27А, во второй строке  — аналогичные данные для файла 27Б.

Ответ:

Решение. ##

from math import dist

data = []

# Для А/Б

for s in open('27Б.txt'):

x, y = [float(d) for d in s.replace(',', '.').split()]

data.append([x, y])

rast = 0.1

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p, p1) < rast]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

#print(*[len(cl) for cl in clusters]) # - проверяет кол-во кластеров

# 2 кластера для файла A и 3 для файла B

# В случае противоречия меняем rast - это значение (Для A - rast = 1, для B - rast = 0.1)

def centroid(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p, p1)

m.append([s, p])

return min(m)[1]

cen = [centroid(cl) for cl in clusters]

px = sum(x for x, y in cen)/len(cen)

py = sum(y for x, y in cen)/len(cen)

print(int(px*10000), int(py*10000))

Ответ для A: 51318 7467.

Ответ для B: 62068 6005.

Приведём решение Сергея Донец на языке PascalABC.NET.

uses coords;
// Функция определения кластера для файла 27А
function numClA(p: point):=
(p.x in 3.5..6.0) and (p.y in 1.0..4.0) ? 0 :
(p.x in 4.0..7.0) and (p.y in -2.5..0.5) ? 1 : 2;
// Функция определения кластера для файла 27Б
function numClB(p: point):=
(p.x in 3.2..6.0) and (p.y in 1.7..4.6) ? 0 :
(p.x in 3.9..6.3) and (p.y in -1.4..1.5) ? 1 :
(p.x in 7.4..10.4) and (p.y in -2.7..-0.1) ? 2 : 3;
function ProcessFile(fname: string; clusters: integer; clFunc: function(p: point): integer): (integer, integer);
begin
var points := ReadAllText(fname).ToReals(',').Batch(2, \(x,y)->Pnt(x,y)).ToArray;
DrawPoints(points);//по визуализации пишем границы для numClA(зеленые точки), numClB(синие точки)
var centers := ArrGen(clusters, c -> begin
var cl := points.Where(p -> clFunc(p) = c).ToArray;
Result := cl.Length = 0? Pnt(0, 0) : cl.MinBy(p -> cl.Sum(q -> Distance(p, q)));
//Result := cl.MinBy(p -> cl.Sum(q -> Distance(p, q)));
end);
Result := (Trunc(centers.Average(p -> p.x) * 10000),
Trunc(centers.Average(p -> p.y) * 10000));
end;
begin
var (aX, aY) := ProcessFile('27А.txt', 2, numClA);
var (bX, bY) := ProcessFile('27Б.txt', 3, numClB);
Println('Ответ для A: ', aX, ' ', aY);
Println('Ответ для B: ', bX, ' ', bY);
end.

№ п/п	№ задания	Ответ
1	76242	51318 7467 62068 6005

Ключ