Задание 27. Информатика. ЕГЭ. Поляков-7612
- Просмотры: 196
- Изменено: 24 ноября 2024
(В. Шубинкин) При проведении эксперимента заряженные частицы попадают на чувствительный экран размером \(12\) на \(9\) 
условных единиц. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания в условных единицах. При анализе результатов выделяют кластеры – группы точек на экране, в которые попали частицы. Каждая точка принадлежит только одному кластеру. Минимальное (максимальное) расстояние между кластерами – это минимальное (максимальное) расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому. Расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле:
$$
d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
$$
Аномалиями назовём совокупности из не более чем \(10\) точек, каждая из которых находится на расстоянии более одной условной единицы от точек кластеров. Аномалии в расчётах не учитываются. Даны два входных файла (файл A и файл Б). В файле A хранятся данные о частицах двух кластеров. В каждой строке записана информация о расположении на карте одной точки: сначала координата \(x\), затем координата \(y\) (в условных единицах). Известно, что количество точек не превышает \(1000\). В файле Б хранятся данные о трёх кластерах. Известно, что количество точек не превышает \(10~000\). Структура хранения информации о точках в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите минимальное \(d_{min}\) и максимальное \(d_{max}\) расстояния между двумя кластерами. В ответ запишите \(4\) числа: в первой строке целую часть произведения \(d_{min} \times 10~000\), затем целую часть произведения \(d_{max} \times 10~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что один кластер находится в прямоугольника \(0 < x < 5\), \(0 < y < 5\). Второй лежит в прямоугольнике \(5 < x < 11\), \(5 < y < 9\). Остальные точки — это аномалии.
Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид
Видим, что кластер под номером \(0\) лежит в прямоугольнике \(0 < x < 5\), \(5 < y < 9\). Кластер под номером \(1\) находится в прямоугольнике \(1 < x < 6\), \(1 < y < 5\). Кластер под номером \(2\) лежит в прямоугольнике \(7 < x < 11\), \(2 < y < 7\). Минимальное расстояние нужно искать между кластерами \(0\) и \(1\), максимальное — между кластерами \(0\) и \(2\).
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
if 0 < x < 5 and 0 < y < 5:
return 0
elif 5 < x < 11 and 5 < y < 9:
return 1
else:
return -1
case 1:
if 0 < x < 5 and 5 < y < 9:
return 0
elif 1 < x < 6 and 1 < y < 5:
return 1
elif 7 < x < 11 and 2 < y < 7:
return 2
else:
return -1
def dist(point1, point2):
x1, y1 = point1
x2, y2 = point2
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
base = ''
files = ['27A.txt', '27B.txt']
culsters = [2, 3]
for t in [0, 1]:
data = [[], [], []]
fd = open(base + files[t])
fd.readline()
for line in fd:
x, y = map(float, line.replace(',', '.').split())
cl = which_cluster([x, y], t)
if cl > -1:
data[cl].append([x, y])
min_cl = [[(0, 1)], [(0, 1)]]
max_cl = [[(0, 1)], [(0, 2)]]
dmin = 10**10
dmax = 0
for c in min_cl[t]:
for p1 in data[c[0]]:
for p2 in data[c[1]]:
dmin = min(dmin, dist(p1, p2))
for c in max_cl[t]:
for p1 in data[c[0]]:
for p2 in data[c[1]]:
dmax = max(dmax, dist(p1, p2))
print(int(dmin * 10000), int(dmax*10000))
Ответ:
\(40112 \,\, 103021\)
\(20063 \,\, 94283\)