Задание 27 ЕГЭ по информатике · 76B8BD
Кластеры точек и звёздВысокаяКЭС 4.1
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной H и W, а прямоугольники кластеров не пересекались. Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
В файле А хранятся координаты точек двух кластеров, где H=6 и W=4,5 для каждого кластера. В файле Б хранятся координаты точек трёх кластеров, где H=6 и W=5 для каждого кластера. В файле Б имеются ровно три лишние точки-аномалии, которые не относятся ни к одному кластеру.
Для файла А найдите суммы абсцисс и ординат центров кластеров: Px и Py. Для файла Б найдите минимальное и максимальное расстояния между центрами различных кластеров: Q1 и Q2.
1_76B8BD.zipВ файле А хранятся координаты точек двух кластеров, где H=6 и W=4,5 для каждого кластера. В файле Б хранятся координаты точек трёх кластеров, где H=6 и W=5 для каждого кластера. В файле Б имеются ровно три лишние точки-аномалии, которые не относятся ни к одному кластеру.
Для файла А найдите суммы абсцисс и ординат центров кластеров: Px и Py. Для файла Б найдите минимальное и максимальное расстояния между центрами различных кластеров: Q1 и Q2.
Показать ответ
107002 323741; 58778 151839
Подсказки (3)
- Какие группы точек можно заключить в непересекающиеся прямоугольники заданных размеров?
- Для каждого кластера переберите точки и вычислите сумму расстояний от выбранной точки до остальных точек этого кластера.
- После определения центров вычислите Px, Py, все попарные расстояния между центрами кластеров файла Б, а затем умножьте требуемые величины на 10000 и возьмите целые части.
Решение
1. Сначала необходимо прочитать координаты точек из файлов А и Б и разделить точки на кластеры по условию о прямоугольниках заданных размеров.
2. Для каждого кластера следует найти точку, для которой сумма евклидовых расстояний до всех остальных точек кластера минимальна. Эта точка является центром кластера.
3. Для файла А вычисляются суммы координат центров: Px=∑xi и Py=∑yi.
4. Для файла Б три аномальные точки исключаются, после чего вычисляются все попарные расстояния между тремя центрами. Минимальное из них равно Q1, максимальное — Q2.
5. Числа в ответе получают как абсолютные значения целых частей произведений Px×10000, Py×10000, Q1×10000 и Q2×10000.
2. Для каждого кластера следует найти точку, для которой сумма евклидовых расстояний до всех остальных точек кластера минимальна. Эта точка является центром кластера.
3. Для файла А вычисляются суммы координат центров: Px=∑xi и Py=∑yi.
4. Для файла Б три аномальные точки исключаются, после чего вычисляются все попарные расстояния между тремя центрами. Минимальное из них равно Q1, максимальное — Q2.
5. Числа в ответе получают как абсолютные значения целых частей произведений Px×10000, Py×10000, Q1×10000 и Q2×10000.
Частые ошибки
- Учитывают три аномальные точки файла Б при поиске центров.
- Используют среднее арифметическое координат вместо точки с минимальной суммой расстояний.
- Сравнивают расстояния между всеми точками вместо расстояний между центрами кластеров.
- Забывают взять абсолютную величину целой части произведения на 10000.
Источник: Открытый банк ФИПИ
Похожие задания
27Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 0D9B7C27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 577EED27Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 7B95E827Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 82E6AD27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 90EECD27Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…Кластеры точек и звёзд · 9C15B927Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.