Информатика. ЕГЭ
Задание 27. Информатика. ЕГЭ 2026. Статград. 16.12.2025
- Просмотры: 2125
- Изменено: 28 января 2026
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на \(N\) непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной \(H\) и \(W,\) причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Диаметром кластера назовём максимальное расстояние между двумя точками в кластере. Для каждого кластера гарантируется, что диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$d(A, \, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$ В файле А хранятся данные о звёздах двух кластеров, где \(H = 3,\) \(W = 4\) для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата \(x,\) затем координата \(y.\) Значения даны в условных единицах. Известно, что количество звёзд не превышает \(1000.\)
В файле Б хранятся данные о звёздах трёх кластеров, где \(H = 6,\) \(W = 5\) для каждого кластера. Известно, что количество звёзд не превышает \(10000.\) Структура хранения информации о звёздах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А найдите пары точек, которые образуют диаметр каждого кластера. Затем вычислите два числа: \(P_x\) – минимальную из сумм абсцисс этих точек для всех кластеров и \(P_y\) – минимальную из сумм ординат этих точек для всех кластеров. Для файла Б найдите два числа: \(Q_1\) – диаметр кластера с минимальным количеством точек и \(Q_2\) – максимальное расстояние от точки, образующей диаметр одного кластера, до точки, образующей диаметр другого кластера.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютного значения произведения \(P_x \times 10000,\) затем целую часть абсолютного значения произведения \(P_y \times 10000;\) во второй строке – сначала целую часть произведения \(Q_1\times 10000,\) затем целую часть произведения \(Q_2 \times 10000.\)
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение:
Python
from math import dist
base = ''
files = ['27A.txt', '27B.txt']
eps = 1
for t in (0, 1):
data = [tuple(map(float, line.split())) for line in open(base + files[t])]
clusters = []
while data:
clusters.append([data.pop(0)])
for p in clusters[-1]:
neigh = [pt for pt in data if dist(p, pt) < eps]
clusters[-1] += neigh
for pt in neigh:
data.remove(pt)
clusters = [cl for cl in clusters if len(cl) > 1]
clusters.sort(key=lambda cl: len(cl))
#print(len(clusters), [len(cl) for cl in clusters])
diameters = []
for cl in clusters:
dmax = 0
pair = None
for i in range(len(cl) - 1):
for j in range(i + 1, len(cl)):
d = dist(cl[i], cl[j])
if d > dmax:
dmax = d
pair = (cl[i], cl[j])
diameters.append((pair, dmax))
#print(diameters)
if t == 0:
px = min(pt[0][0] + pt[1][0] for pt, d in diameters)
py = min(pt[0][1] + pt[1][1] for pt, d in diameters)
print(int(px * 10000), int(py * 10000))
else:
q1 = diameters[0][1]
q2 = 0
for i in range(len(diameters) - 1):
for j in range(i + 1, len(diameters)):
d1 = dist(diameters[i][0][0], diameters[j][0][0])
d2 = dist(diameters[i][0][0], diameters[j][0][1])
d3 = dist(diameters[i][0][1], diameters[j][0][0])
d4 = dist(diameters[i][0][1], diameters[j][0][1])
q2 = max(q2, d1, d2, d3, d4)
print(int(q1 * 10_000), int(q2 * 10_000))
Ответ:
\(145015 \,\, 313020\)
\(29254 \,\, 488624\)
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года