№27 — примеры решений
Один эталонный разбор.
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2).
В файле A хранятся данные о звёздах двух кластеров, где H=6,5, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6,5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: P1 - минимальное расстояние от точки с координатами (1,0; 1,0) до центра кластера, и P2 - максимальное расстояние от этой же точки до центра кластера.
Для файла B определите координаты центра каждого кластера, затем найдите два числа: Q1 - в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 1,2 от центра кластера, и Q2 - в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 0,75 от центра кластера.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке - сначала целую часть произведения P1 × 10000, затем целую часть произведения P2 × 10000; во второй строке - сначала Q1, затем Q2.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_271.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 10:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
P = [1.0, 1.0]
d1 = dist(c1, P)
d2 = dist(c2, P)
P1 = min(d1, d2)
P2 = max(d1, d2)
print(int(P1 * 10000), int(P2 * 10000))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_271.txt')
k1 = [] # y < 16
k2 = [] # 16 <= y < 22
k3 = [] # y >= 22
for h in pts:
if h[1] < 16:
k1.append(h)
elif h[1] < 22:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
# самый большой кластер
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
big_i = 0
for i in range(1, 3):
if len(clusters[i]) > len(clusters[big_i]):
big_i = i
big = clusters[big_i]
bc = centers[big_i]
Q1 = 0
Q2 = 0
for p in big:
d = dist(p, bc)
if d <= 1.2:
Q1 += 1
if d <= 0.75:
Q2 += 1
print(Q1, Q2)
Ответ:58605 128643 358 203
📚
Все задачи с разбором
16
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить на N непересекающихся подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2).
В файле A хранятся координаты точек двух кластеров, где H = 6,5 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.
В файле Б хранятся координаты точек трёх кластеров, где H = 6,5 и W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле А.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: A1 — минимальное количество точек в кластере и A2 — сумму расстояний от центров кластеров до точки с координатами (-1,0; 1,3).
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1 — число точек, находящихся на расстоянии не более 1,6 от центра, не включая центр, в кластере со средним количеством точек, и B2 — максимальное расстояние от центра кластера с наибольшим количеством точек до другой точки этого кластера.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке — сначала A1, затем целую часть произведения A2 × 10 000; во второй строке сначала B1, затем целую часть произведения B2 × 10 000.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_272.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 15:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
A1 = min(len(k1), len(k2))
P = [-1.0, 1.3]
A2 = dist(c1, P) + dist(c2, P)
print(A1, int(A2 * 10000))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_272.txt')
k1 = [] # y > 22 — самый большой
k2 = [] # y <= 22 и x < 24
k3 = [] # y <= 22 и x >= 24
for h in pts:
if h[1] > 22:
k1.append(h)
elif h[0] < 24:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
order = sorted(range(3), key=lambda i: len(clusters[i]))
mid_cluster = clusters[order[1]]
mid_center = centers[order[1]]
big_cluster = clusters[order[2]]
big_center = centers[order[2]]
B1 = 0
for p in mid_cluster:
if p == mid_center:
continue
if dist(p, mid_center) <= 1.6:
B1 += 1
B2 = 0
for p in big_cluster:
if p == big_center:
continue
d = dist(p, big_center)
if d > B2:
B2 = d
print(B1, int(B2 * 10000))
Ответ:301 319272 182 26825
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x₂ − x₁)² + (y₂ − y₁)²).
В файле A хранятся данные о звёздах двух кластеров, где H = 6,5, W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H = 6,5, W = 5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: A1 — максимальное количество точек в кластере и A2 — сумму расстояний от центров кластеров до точки с координатами (1,0; 1,5). Для файла B определите координаты центра каждого кластера, затем найдите два числа: B1 — число точек, находящихся на расстоянии не более 1,2 от центра кластера, не включая центр, в кластере со средним количеством точек и B2 — минимальное расстояние от центра кластера с наибольшим количеством точек до другой точки этого кластера. Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке — сначала A1, затем целую часть произведения A2 × 10 000; во второй строке — сначала B1, затем целую часть произведения B2 × 10 000.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_273.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 15:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
A1 = max(len(k1), len(k2))
P = [1.0, 1.5]
A2 = dist(c1, P) + dist(c2, P)
print(A1, int(A2 * 10000))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_273.txt')
k1 = [] # y > 22
k2 = [] # y <= 22 и x < 24
k3 = [] # y <= 22 и x >= 24
for h in pts:
if h[1] > 22:
k1.append(h)
elif h[0] < 24:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
order = sorted(range(3), key=lambda i: len(clusters[i]))
mid_cluster = clusters[order[1]]
mid_center = centers[order[1]]
big_cluster = clusters[order[2]]
big_center = centers[order[2]]
B1 = 0
for p in mid_cluster:
if p == mid_center:
continue
if dist(p, mid_center) <= 1.2:
B1 += 1
B2 = 10**18
for p in big_cluster:
if p == big_center:
continue
d = dist(p, big_center)
if d < B2:
B2 = d
print(B1, int(B2 * 10000))
Ответ:344 294354 152 528
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)² + (y2 − y1)²).
В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: Px — минимальную из абсцисс центров кластеров, и Py — минимальную из ординат центров кластеров. Для файла Б найдите два числа: Q1 — расстояние между центрами кластеров с минимальным и максимальным количеством точек, и Q2 — максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке — сначала абсолютную величину целой части произведения Px × 10 000, затем абсолютную величину целой части произведения Py × 10 000; во второй строке — сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_274.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 9:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = min(c1[0], c2[0])
Py = min(c1[1], c2[1])
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_274.txt')
# отбрасываем 3 аномалии (точки далеко вне трёх кластеров)
clean = []
for h in pts:
if 0 <= h[0] <= 25 and 0 <= h[1] <= 30:
clean.append(h)
k1 = [] # y < 19
k2 = [] # y >= 19 и x < 18
k3 = [] # y >= 19 и x >= 18
for h in clean:
if h[1] < 19:
k1.append(h)
elif h[0] < 18:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
order = sorted(range(3), key=lambda i: len(clusters[i]))
small_center = centers[order[0]]
big_center = centers[order[2]]
Q1 = dist(small_center, big_center)
Q2 = 0
for cl, cen in zip(clusters, centers):
for p in cl:
d = dist(p, cen)
if d > Q2:
Q2 = d
print(int(Q1 * 10000), int(Q2 * 10000))
Ответ:38471 61225 142058 25299
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:
d(A, B) = √((x2 − x1)² + (y2 − y1)²)
В файле A хранятся данные о звёздах двух кластеров, где H=11, W=11 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=13, W=13 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10000, затем целую часть абсолютного значения произведения Py × 10000 для файла A, во второй строке — аналогичные данные для файла B. Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2710.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 0:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2710.txt')
k1 = []
k2 = []
k3 = []
for h in pts:
if h[0] > 20:
k1.append(h)
elif h[0] > 8:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
Ответ:26216 24182 150891 63754
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию получившихся изображений звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле d(A, B) = √((x₂ − x₁)² + (y₂ − y₁)²). В файле A хранятся координаты точек двух кластеров, где H = 6, W = 6 для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000. В файле Б хранятся координаты точек трёх кластеров, где H = 5, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Pₓ — среднее арифметическое абсцисс центров кластеров, и Pᵧ — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Pₓ × 10 000, затем абсолютное значение целой части произведения Pᵧ × 10 000 для файла A, во второй строке — аналогичные данные для файла Б.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
import openpyxl
def read_points(name):
wb = openpyxl.load_workbook(name)
ws = wb.active
pts = []
for row in ws.iter_rows(values_only=True):
if row is None or len(row) < 2:
continue
try:
x = float(row[0])
y = float(row[1])
except (TypeError, ValueError):
continue
pts.append([x, y])
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_275.xlsx')
k1 = []
k2 = []
for h in pts:
if h[1] < 5:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_275.xlsx')
k1 = [] # x < 0
k2 = [] # x >= 0 и y < 7
k3 = [] # x >= 0 и y >= 7
for h in pts:
if h[0] < 0:
k1.append(h)
elif h[1] < 7:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
Ответ:43789 62202 14271 54727
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)² + (y2 − y1)²). В файле A хранятся данные о звёздах двух кластеров, где H=6, W=6 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H=9, W=9 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целая часть абсолютного значения произведения Px × 10000, затем целая часть абсолютного значения произведения Py × 10000 для файла A, во второй строке – аналогичные данные для файла B. Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_276.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 0:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_276.txt')
k1 = []
k2 = []
k3 = []
for h in pts:
if h[0] < -5:
k2.append(h)
elif h[1] > -1:
k1.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
Ответ:10592 6300 15981 37287
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются.
Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)² + (y2 − y1)²). В файле A хранятся данные о звёздах двух кластеров, где H = 6, W = 6 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H = 9, W = 9 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px — среднее арифметическое абсцисс центров кластеров, и Py — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целая часть абсолютного значения произведения Px × 10000, затем целая часть абсолютного значения произведения Py × 10000 для файла A, во второй строке — аналогичные данные для файла B. Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_277.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 0:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_277.txt')
k1 = []
k2 = []
k3 = []
for h in pts:
if h[1] > 5:
k1.append(h)
elif h[1] < -7:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
Ответ:28603 10294 61260 11206
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2).
В файле A хранятся данные о звёздах двух кластеров, где H=5, W=6 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=9, W=9 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10000, затем целую часть абсолютного значения произведения Py × 10000 для файла A, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_279.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > -1:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_279.txt')
k1 = []
k2 = []
k3 = []
for h in pts:
if h[1] < 0:
k3.append(h)
elif h[0] < -6:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
Ответ:32540 13646 47031 25263
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2).
В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=5, W=6 для каждого кластера. Известно, что количество звёзд не превышает 1000. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px - максимальную из абсцисс центров кластеров, и Py - максимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Qx - разность абсцисс центров кластеров с минимальным и максимальным количеством точек, и Qy - разность ординат центров кластеров с минимальным и максимальным количеством точек. Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке - сначала целую часть абсолютного значения произведения Px × 10000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке - сначала целую часть абсолютного значения произведения Qx × 10000, затем целую часть абсолютного значения произведения Qy × 10000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2711.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 12:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = max(c1[0], c2[0])
Py = max(c1[1], c2[1])
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2711.txt')
# отбрасываем 3 аномалии
clean = []
for h in pts:
if 0 <= h[0] <= 20 and 0 <= h[1] <= 30:
clean.append(h)
k1 = [] # y < 12
k2 = [] # 12 <= y < 21
k3 = [] # y >= 21
for h in clean:
if h[1] < 12:
k1.append(h)
elif h[1] < 21:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
order = sorted(range(3), key=lambda i: len(clusters[i]))
small_center = centers[order[0]]
big_center = centers[order[2]]
Qx = small_center[0] - big_center[0]
Qy = small_center[1] - big_center[1]
print(abs(int(Qx * 10000)), abs(int(Qy * 10000)))
Ответ:69663 192156 867 161306
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2)
В файле A хранятся данные о звёздах двух кластеров, где H=6, W=5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах 3 кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле В аналогична файлу A.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: Px - сумму абсцисс центров кластеров, и Py - сумму ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 - минимальное расстояние между центрами различных кластеров, и Q2 - максимальное расстояние между центрами кластеров.
В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения Px × 10000, затем абсолютную величину целой части произведения Py × 10 000; во второй строке - сначала абсолютную величину целой части произведения Q1 ×10 000, затем абсолютную величину целой части произведения Q2 × 10 000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2712.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 15:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = c1[0] + c2[0]
Py = c1[1] + c2[1]
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2712.txt')
clean = []
for h in pts:
if 0 <= h[0] <= 30 and 10 <= h[1] <= 40:
clean.append(h)
k1 = []
k2 = []
k3 = []
for h in clean:
if h[0] < 12:
k1.append(h)
elif h[0] < 19:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
centers = [c1, c2, c3]
d12 = dist(centers[0], centers[1])
d13 = dist(centers[0], centers[2])
d23 = dist(centers[1], centers[2])
Q1 = min(d12, d13, d23)
Q2 = max(d12, d13, d23)
print(abs(int(Q1 * 10000)), abs(int(Q2 * 10000)))
Ответ:107002 323741 58778 151839
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле: d(A, B) = √((x₂ − x₁)² + (y₂ − y₁)²)
В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле B аналогична файлу A.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных.
Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: Pₓ - сумму абсцисс центров кластеров, и Pᵧ - сумму ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q₁ - минимальное расстояние от центра кластера до начала координат, и Q₂ - максимальное расстояние от центра кластера до начала координат.
В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения Pₓ × 10000, затем абсолютную величину целой части произведения Pᵧ × 10 000; во второй строке - сначала целую часть произведения Q₁ × 10 000, затем целую часть произведения Q₂ × 10 000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2713.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 10:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = c1[0] + c2[0]
Py = c1[1] + c2[1]
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2713.txt')
clean = []
for h in pts:
if 0 <= h[0] <= 30 and 0 <= h[1] <= 30:
clean.append(h)
k1 = []
k2 = []
k3 = []
for h in clean:
if h[0] > 18:
k1.append(h)
elif h[1] < 21:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
centers = [c1, c2, c3]
ds = [sqrt(c[0]*c[0] + c[1]*c[1]) for c in centers]
Q1 = min(ds)
Q2 = max(ds)
print(int(Q1 * 10000), int(Q2 * 10000))
Ответ:110156 196632 224871 273226
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле: d(A,B)=((x1−x2)2+(y1−y2)2)0.5
Аномалиями назовём звёзды, находящиеся на расстоянии более пяти условных единиц от звёзд кластеров. При расчётах аномалии учитывать не нужно.
В файле A хранятся данные о звёздах двух кластеров, где H=16, W=16 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=12, W=12 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу A.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла A определите координаты центра каждого кластера, затем вычислите два числа: Px - сумма абсцисс центров кластеров, и Py - сумма ординат центров кластеров.
Для файла Б определите координаты центра каждого кластера, затем вычислите два числа: Q1 - минимальное расстояние от центра до начала координат, и Q2 - максимальное расстояние от центра до начала координат.
Гарантируется, что во всех кластерах количество точек различно.
В ответе запишите четыре числа: в первой строке - сначала целую часть абсолютного значения произведения Px x 10 000, затем целую часть абсолютного значения произведения Py x 10 000; во второй строке - сначала целую часть абсолютного значения произведения Q1 x 10 000, затем целую часть абсолютного значения произведения Q2 x 10 000.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2714.txt')
k1 = []
k2 = []
for h in pts:
if h[0] < -20:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = c1[0] + c2[0]
Py = c1[1] + c2[1]
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2714.txt')
# отбрасываем 3 аномалии: точки с x > -30 и y > -15
clean = []
for h in pts:
if not (h[0] > -30 and h[1] > -15):
clean.append(h)
k1 = [] # x < -28 — третий кластер (с y около 0)
k2 = [] # -28 <= x < -10 — второй
k3 = [] # x >= -10 — первый
for h in clean:
if h[0] < -28:
k1.append(h)
elif h[0] < -10:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
centers = [c1, c2, c3]
ds = [sqrt(c[0]*c[0] + c[1]*c[1]) for c in centers]
Q1 = min(ds)
Q2 = max(ds)
print(abs(int(Q1 * 10000)), abs(int(Q2 * 10000)))
Ответ:404241 1013671 349898 471860
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A, B) = √((x2 − x1)2 + (y2 − y1)2)
В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: Pₓ - сумму абсцисс центров кластеров, и Pᵧ - сумму ординат центров кластеров. Для файла Б найдите два числа: Q1 - минимальное расстояние между точками, принадлежащими двум различным кластерам, и Q2 - максимальное расстояние между точками, принадлежащими двум различным кластерам.
В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения Pₓ × 10000, затем абсолютную величину целой части произведения Pᵧ × 10000; во второй строке - сначала целую часть произведения Q1 × 10000, затем целую часть произведения Q2 × 10 000.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2715.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 12:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = c1[0] + c2[0]
Py = c1[1] + c2[1]
print(abs(int(Px * 10000)), abs(int(Py * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2715.txt')
clean = []
for h in pts:
if 0 <= h[0] <= 30 and 0 <= h[1] <= 25:
clean.append(h)
k1 = []
k2 = []
k3 = []
for h in clean:
if h[0] > 20:
k1.append(h)
elif h[1] < 14:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
Q1 = 10**18
Q2 = 0
for i in range(3):
for j in range(i + 1, 3):
for p in clusters[i]:
for q in clusters[j]:
d = dist(p, q)
if d < Q1:
Q1 = d
if d > Q2:
Q2 = d
print(int(Q1 * 10000), int(Q2 * 10000))
Ответ:92256 258611 33863 170816
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле: d(A, B) = √((x₂ − x₁)2 + (y₂ − y₁)2)
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y.
Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звёздах в файле B аналогична файлу A.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Pₓ – среднее арифметическое абсцисс центров кластеров, и Pᵧ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Pₓ × 10000, затем целую часть произведения Pᵧ × 10000 для файла A, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(f) for f in x]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2716.txt')
k1 = []
k2 = []
for h in pts:
if h[1] > 3:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
Px = (c1[0] + c2[0]) / 2
Py = (c1[1] + c2[1]) / 2
print(int(Px * 10000), int(Py * 10000))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2716.txt')
k1 = []
k2 = []
k3 = []
for h in pts:
if h[1] > 7:
k1.append(h)
elif h[0] > 4:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
Px = (c1[0] + c2[0] + c3[0]) / 3
Py = (c1[1] + c2[1] + c3[1]) / 3
print(int(Px * 10000), int(Py * 10000))
Ответ:10738 30730 37522 51277
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями планет, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Для каждой планеты дана характеристика: тип цвета, тип светимости и её размер в соответствии с таблицей.
| Обозначение | Цвет |
|---|
| G | белый |
| J | зелёный |
| L | синий |
| N | оранжевый |
| Y | красный |
| S | голубой |
| Z | жёлтый |
| Обозначение | Размер |
|---|
| I | планет |
| II | карлик |
| III | гигант |
| IV | сверхгигант |
| V | мега-гигант |
| VI | супер-гигант |
| VII | пухляк |
Полученные значения записаны в характеристике слитно: обозначение цвета, светимость (обозначается арабской цифрой) и размер планеты.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x
1, y
1) и B(x
2, y
2) вычисляется по формуле: d(A, B) = √((x
2 − x
1)
2 + (y
2 − y
1)
2).
В файле A хранятся данные о звёздах двух кластеров, где H = 6,5 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y, а затем характеристика звезды. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H = 6,5 и W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична файлу A.
Для файла A определите координаты центра каждого кластера, затем найдите два числа: A
1 – минимальное расстояние от центра кластера с наименьшим количеством точек до красного гиганта, и A
2 – максимальное расстояние от центра кластера с наименьшим количеством точек до красного гиганта.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B
1 – минимальное расстояние между двумя различными жёлтыми сверхгигантами, расположенными в одном и том же кластере, и B
2 – расстояние между центрами кластеров с минимальным и максимальным количеством жёлтых сверхгигантов.
В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютного значения произведения A
1 × 10 000, затем целую часть абсолютного значения произведения A
2 × 10 000; во второй строке – сначала целую часть абсолютного значения произведения B
1 × 10 000, затем целую часть абсолютного значения произведения B
2 × 10 000.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(x[0]), float(x[1]), x[2]]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2717.txt')
k1 = []
k2 = []
for h in pts:
if h[1] < 10:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
# меньший кластер
if len(k1) < len(k2):
small_center = c1
else:
small_center = c2
# красные гиганты: Y...III
red_giants = []
for h in pts:
if h[2].startswith('Y') and h[2].endswith('III'):
red_giants.append(h)
A1 = 10**18
A2 = 0
for rg in red_giants:
d = dist(small_center[:2], rg[:2])
if d < A1:
A1 = d
if d > A2:
A2 = d
print(abs(int(A1 * 10000)), abs(int(A2 * 10000)))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2717.txt')
k1 = [] # y < 16
k2 = [] # 16 <= y < 22
k3 = [] # y >= 22
for h in pts:
if h[1] < 16:
k1.append(h)
elif h[1] < 22:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
# жёлтые сверхгиганты: Z...IV
B1 = 10**18
yellow_counts = []
for cl in clusters:
ys = [p for p in cl if p[2].startswith('Z') and p[2].endswith('IV')]
yellow_counts.append(len(ys))
for i in range(len(ys)):
for j in range(i + 1, len(ys)):
d = dist(ys[i][:2], ys[j][:2])
if d < B1:
B1 = d
# центры кластеров с min и max количеством жёлтых сверхгигантов
imax = yellow_counts.index(max(yellow_counts))
imin = yellow_counts.index(min(yellow_counts))
B2 = dist(centers[imax][:2], centers[imin][:2])
print(abs(int(B1 * 10000)), abs(int(B2 * 10000)))
Ответ:4940 74302 1825 189261
Условие
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Гарантируется, что во всех кластерах количество точек различно.
Для каждой звезды задана характеристика – набор символов, включающий спектральный класс (обозначается латинской буквой), подкласс светимости (обозначается арабской цифрой) и класс светимости (обозначается римской цифрой).
Спектральный класс звезды определяется в соответствии с таблицей:
| Спектральный класс звезды | O | B | A | F | G | K | M |
|---|
| Голубая | Бело-голубая | Белая | Желто-белая | Желтая | Оранжевая | Красная |
Класс светимости звезды определяется в соответствии с таблицей:
| Класс светимости звезды | I | II | III | IV | V | VI | VII |
|---|
| Сверхгиганты | Яркие гиганты | Гиганты | Субгиганты | Карлики | Субкарлики | Белые карлики |
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости А (х
1, y
1) и B (х
2, y
2) вычисляется по формуле: √((х
2 − х
1)
2 + (y
2 − y
1)
2).
В файле А хранятся данные о звёздах двух кластеров, где Н = 5 и W = 4 для каждого кластера. В каждой строке записана информация одной звезды: координата х, координата у и её характеристика. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где Н = 3 и W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации о звёздах в файле Б аналогична структуре в файле А.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: A1 – абсциссу ближайшего белого гиганта к центру кластера с наименьшим количеством точек, и A2 – ординату ближайшего белого гиганта к центру кластера с наименьшим количеством точек.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1 – расстояние между центрами кластеров с наибольшим и наименьшим количеством красных сверхгигантов, и B2 – максимальное расстояние между двумя жёлтыми карликами, находящимися в одном кластере.
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения A1 × 10 000, затем целую часть произведения A2 × 10 000; во второй строке – сначала целую часть произведения B1 × 10 000, затем целую часть произведения B2 × 10 000.
Решение
from math import *
def find(k):
minsumm = 10**18
minc = []
for c1 in k:
summ = 0
for c2 in k:
summ += dist(c1[:2], c2[:2])
if summ < minsumm:
minsumm = summ
minc = c1
return minc
def read_points(name):
t = open(name)
pts = []
for x in t.readlines():
x = x.replace(',', '.').split()
try:
h = [float(x[0]), float(x[1]), x[2]]
pts.append(h)
except:
pass
return pts
# ---------- ФАЙЛ A ----------
pts = read_points('27_A_2718.txt')
k1 = []
k2 = []
for h in pts:
if h[0] < 25:
k1.append(h)
else:
k2.append(h)
c1 = find(k1)
c2 = find(k2)
if len(k1) < len(k2):
small_center = c1
else:
small_center = c2
def is_white_giant(s):
if not s or s[0] != 'A':
return False
i = 1
while i < len(s) and s[i].isdigit():
i += 1
return s[i:] == 'III'
best = None
best_d = 10**18
for h in pts:
if is_white_giant(h[2]):
d = dist(small_center[:2], h[:2])
if d < best_d:
best_d = d
best = h
A1 = best[0]
A2 = best[1]
print(int(A1 * 10000), int(A2 * 10000))
# ---------- ФАЙЛ B ----------
pts = read_points('27_B_2718.txt')
k1 = [] # y > 14
k2 = [] # y < 8
k3 = [] # 8 <= y <= 14
for h in pts:
if h[1] > 14:
k1.append(h)
elif h[1] < 8:
k2.append(h)
else:
k3.append(h)
c1 = find(k1)
c2 = find(k2)
c3 = find(k3)
clusters = [k1, k2, k3]
centers = [c1, c2, c3]
def is_red_supergiant(s):
if not s or s[0] != 'M':
return False
i = 1
while i < len(s) and s[i].isdigit():
i += 1
return s[i:] == 'I'
def is_yellow_dwarf(s):
if not s or s[0] != 'G':
return False
i = 1
while i < len(s) and s[i].isdigit():
i += 1
return s[i:] == 'V'
red_counts = []
for cl in clusters:
red_counts.append(sum(1 for p in cl if is_red_supergiant(p[2])))
imax = red_counts.index(max(red_counts))
imin = red_counts.index(min(red_counts))
B1 = dist(centers[imax][:2], centers[imin][:2])
B2 = 0
for cl in clusters:
yd = [p for p in cl if is_yellow_dwarf(p[2])]
for i in range(len(yd)):
for j in range(i + 1, len(yd)):
d = dist(yd[i][:2], yd[j][:2])
if d > B2:
B2 = d
print(int(B1 * 10000), int(B2 * 10000))
Ответ:390205 182699 60306 16460