Задание 27 ЕГЭ по информатике · 90EECD
Кластеры точек и звёздВысокаяКЭС 4.1
Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить точки на непересекающиеся кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной H и W, а прямоугольники не пересекались. Центр кластера — точка этого кластера, сумма расстояний от которой до остальных точек минимальна. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют цветам: голубой, бело-голубой, белый, жёлто-белый, жёлтый, оранжевый, красный. Каждый спектральный класс имеет подклассы от 0 до 9. Классы светимости обозначаются римскими цифрами от I до VII: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.
В файле А содержится информация о точках двух кластеров. Для каждого кластера H=6,0 и W=5,5. Для файла А определите координаты центров кластеров, затем найдите координаты Ax и Ay бело-голубого яркого гиганта, ближайшего к центру кластера, содержащего наибольшее количество точек.
В файле Б содержатся координаты точек трёх кластеров. Для каждого кластера H=6,0 и W=5,5. Определите координаты центров кластеров, затем найдите B1 — расстояние между центрами кластеров с наименьшим и наибольшим количеством жёлтых карликов, и B2 — наибольшее расстояние между оранжевыми карликами одного кластера.
В ответе запишите четыре числа: в первой строке — целые части ∣Ax×10000∣ и ∣Ay×10000∣; во второй строке — целые части B1×10000 и B2×10000.
Структура файлов приведена в условии. Количество точек в файле А не превышает 2000, в файле Б — 10000.
1_90EECD.zipКаждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют цветам: голубой, бело-голубой, белый, жёлто-белый, жёлтый, оранжевый, красный. Каждый спектральный класс имеет подклассы от 0 до 9. Классы светимости обозначаются римскими цифрами от I до VII: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.
В файле А содержится информация о точках двух кластеров. Для каждого кластера H=6,0 и W=5,5. Для файла А определите координаты центров кластеров, затем найдите координаты Ax и Ay бело-голубого яркого гиганта, ближайшего к центру кластера, содержащего наибольшее количество точек.
В файле Б содержатся координаты точек трёх кластеров. Для каждого кластера H=6,0 и W=5,5. Определите координаты центров кластеров, затем найдите B1 — расстояние между центрами кластеров с наименьшим и наибольшим количеством жёлтых карликов, и B2 — наибольшее расстояние между оранжевыми карликами одного кластера.
В ответе запишите четыре числа: в первой строке — целые части ∣Ax×10000∣ и ∣Ay×10000∣; во второй строке — целые части B1×10000 и B2×10000.
Структура файлов приведена в условии. Количество точек в файле А не превышает 2000, в файле Б — 10000.
Показать ответ
84057 196841; 116881 38914
Подсказки (3)
- Сначала определите принадлежность каждой точки кластеру по условию о прямоугольниках со сторонами H=6,0 и W=5,5.
- Для центра каждого кластера переберите все его точки и выберите точку с минимальной суммой евклидовых расстояний до остальных точек этого кластера.
- После нахождения кластеров и их центров отфильтруйте звёзды по спектральному классу и классу светимости, затем вычислите требуемые расстояния и умножьте результаты на 10000.
Решение
1. Из файлов необходимо считать координаты и обозначения классов всех звёзд. Для звёзд класса светимости VII спектральный класс и подкласс отсутствуют.
2. Разделить точки на кластеры. Для каждой пары точек можно использовать геометрическое условие принадлежности одному прямоугольнику со сторонами 6,0 и 5,5; гарантии задачи обеспечивают единственность разбиения.
3. Для каждого кластера перебрать все точки. Для каждой точки вычислить сумму расстояний до остальных точек кластера и выбрать точку с минимальной суммой. Это и есть центр кластера.
4. В файле А выбрать кластер с наибольшим количеством точек, затем среди бело-голубых ярких гигантов выбрать звезду, ближайшую к центру этого кластера. Получить Ax и Ay.
5. В файле Б для каждого кластера посчитать жёлтых карликов. Найти кластеры с минимальным и максимальным количеством таких звёзд и вычислить расстояние между их центрами — это B1.
6. Для каждого кластера рассмотреть все пары оранжевых карликов и найти максимальное расстояние между точками одной пары. Максимальное из этих расстояний — B2.
7. Умножить ∣Ax∣, ∣Ay∣, B1 и B2 на 10000, взять целые части и записать в требуемом порядке.
2. Разделить точки на кластеры. Для каждой пары точек можно использовать геометрическое условие принадлежности одному прямоугольнику со сторонами 6,0 и 5,5; гарантии задачи обеспечивают единственность разбиения.
3. Для каждого кластера перебрать все точки. Для каждой точки вычислить сумму расстояний до остальных точек кластера и выбрать точку с минимальной суммой. Это и есть центр кластера.
4. В файле А выбрать кластер с наибольшим количеством точек, затем среди бело-голубых ярких гигантов выбрать звезду, ближайшую к центру этого кластера. Получить Ax и Ay.
5. В файле Б для каждого кластера посчитать жёлтых карликов. Найти кластеры с минимальным и максимальным количеством таких звёзд и вычислить расстояние между их центрами — это B1.
6. Для каждого кластера рассмотреть все пары оранжевых карликов и найти максимальное расстояние между точками одной пары. Максимальное из этих расстояний — B2.
7. Умножить ∣Ax∣, ∣Ay∣, B1 и B2 на 10000, взять целые части и записать в требуемом порядке.
Частые ошибки
- Используют среднее арифметическое координат вместо определения центра как точки кластера.
- Считают расстояния между любыми оранжевыми карликами разных кластеров.
- Путают бело-голубой спектральный класс $B$ с классом светимости.
- Забывают взять целую часть произведения после умножения на $10000$.
Источник: Открытый банк ФИПИ
Похожие задания
27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 577EED27Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 76B8BD27Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 7B95E827Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 82E6AD27Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…Кластеры точек и звёзд · 9C15B927Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB27Задание выполняется с использованием прилагаемых файлов. В файлах A и Б записаны координаты точек на…Кластеры точек и звёзд · B5FB72
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.