Как в ЕГЭ · 20 из 20
№27. Центры скоплений
По мотивам задания №27. Астроном отметил на карте звёзды, и они собрались в скопления. Звёзды одного скопления — цепочкой: от любой до любой можно дойти шагами не длиннее d. Центр скопления — та звезда, от которой сумма расстояний до остальных его звёзд наименьшая. Ответ экзамена — среднее центров по каждой оси, умноженное на 10 000; с 2027 года его пишут одной строкой из двух чисел.
Что сделать
Разбейте звёзды на скопления, найдите центр каждого и верните средние координаты центров, умноженные на 10 000.
Что приходит
tochki— звёзды: пары(x, y), координаты положительные, дробныеd— наибольший шаг внутри скопления
Что вернуть
Пару (Px, Py) — целые части средних x и y центров, умноженных на 10 000.
Допишите функцию centry в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
с графикой когда тесты пройдут, ответ вашей функции нарисуется · все задачи с графикой
Звёзды (1, 1), (2, 1), (3, 1) и (10, 10) при d = 1,5. Первые три — одно скопление: шаги по 1. Его центр — (2, 1): сумма расстояний 2, у краёв — 3. Четвёртая звезда — скопление сама по себе, центр — она. Среднее центров — (6; 5,5), ответ (60000, 55000).
centry([(1, 1), (2, 1), (3, 1), (10, 10)], 1.5)
(60000, 55000)
Две звезды в одном скоплении, если от одной до другой есть цепочка звёзд с шагами не длиннее d (расстояние обычное, по прямой). Центр скопления — его звезда с наименьшей суммой расстояний до остальных звёзд скопления; при равенстве — та, что раньше в списке. У скопления из одной звезды центр — она сама. Px — целая часть от (среднее x центров) · 10 000, Py — так же по y. Звёзд — до двадцати тысяч, скоплений — до нескольких сотен: решение, которое для каждой звезды проверяет все остальные, на таком входе не успевает.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.