Задание 27 ЕГЭ по информатике · 0D9B7C
Кластеры точек и звёздВысокаяКЭС 4.1
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для точек A(x1,y1) и B(x2,y2) расстояние вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют соответственно голубому, бело-голубому, белому, жёлто-белому, жёлтому, оранжевому и красному цвету. Каждый спектральный класс делится на подклассы от 0 до 9 в порядке уменьшения температуры. Класс светимости обозначается римскими цифрами от I до VII: I — сверхгигант, II — яркий гигант, III — гигант, IV — субгигант, V — карлик, VI — субкарлик, VII — белый карлик.
В файле A хранится информация о точках двух кластеров, где H=6,0 и W=5,5 для каждого кластера. В каждой строке сначала записаны координаты x и y одной звезды, затем для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов записываются слитно. Для звёзд класса светимости VII обозначения спектрального класса и подкласса не указываются. Количество точек не превышает 2000.
В файле Б хранятся координаты точек трёх кластеров при тех же значениях H=6,0 и W=5,5. Количество точек не превышает 10 000. Структура хранения информации аналогична структуре файла А.
Для файла А определите координаты центра каждого кластера, затем найдите абсциссу Ax и ординату Ay оранжевого субкарлика, ближайшего к центру кластера, который содержит наибольшее количество точек.
Для файла Б определите расстояние B1 между центрами кластеров с наименьшим и наибольшим количеством жёлто-белых ярких гигантов и найдите B2 — наибольшее расстояние между белыми яркими гигантами одного кластера.
В ответе запишите четыре числа: в первой строке — целую часть абсолютной величины произведения Ax×10000, затем целую часть абсолютной величины произведения Ay×10000; во второй строке — целую часть произведения B1×10000, затем целую часть произведения B2×10000. Для решения используйте данные из прилагаемых файлов.
1_0D9B7C.zipЦентром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для точек A(x1,y1) и B(x2,y2) расстояние вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют соответственно голубому, бело-голубому, белому, жёлто-белому, жёлтому, оранжевому и красному цвету. Каждый спектральный класс делится на подклассы от 0 до 9 в порядке уменьшения температуры. Класс светимости обозначается римскими цифрами от I до VII: I — сверхгигант, II — яркий гигант, III — гигант, IV — субгигант, V — карлик, VI — субкарлик, VII — белый карлик.
В файле A хранится информация о точках двух кластеров, где H=6,0 и W=5,5 для каждого кластера. В каждой строке сначала записаны координаты x и y одной звезды, затем для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов записываются слитно. Для звёзд класса светимости VII обозначения спектрального класса и подкласса не указываются. Количество точек не превышает 2000.
В файле Б хранятся координаты точек трёх кластеров при тех же значениях H=6,0 и W=5,5. Количество точек не превышает 10 000. Структура хранения информации аналогична структуре файла А.
Для файла А определите координаты центра каждого кластера, затем найдите абсциссу Ax и ординату Ay оранжевого субкарлика, ближайшего к центру кластера, который содержит наибольшее количество точек.
Для файла Б определите расстояние B1 между центрами кластеров с наименьшим и наибольшим количеством жёлто-белых ярких гигантов и найдите B2 — наибольшее расстояние между белыми яркими гигантами одного кластера.
В ответе запишите четыре числа: в первой строке — целую часть абсолютной величины произведения Ax×10000, затем целую часть абсолютной величины произведения Ay×10000; во второй строке — целую часть произведения B1×10000, затем целую часть произведения B2×10000. Для решения используйте данные из прилагаемых файлов.
Показать ответ
76965 201557; 115544 250374
Подсказки (3)
- Сначала разделите точки на кластеры: два кластера для файла A и три кластера для файла Б.
- Для каждой точки вычислите сумму расстояний до остальных точек её кластера. Точка с минимальной суммой является центром кластера.
- Отфильтруйте звёзды по обозначениям спектрального класса и класса светимости, вычислите требуемые расстояния, умножьте результаты на 10000 и отбросьте дробную часть.
Решение
1. Прочитать строки файлов и выделить координаты звёзд, а также их спектральные классы и классы светимости.
2. Разбить точки на кластеры, используя условие о прямоугольниках со сторонами H=6,0 и W=5,5.
3. Для каждого кластера найти точку, минимизирующую сумму расстояний до всех остальных точек этого кластера.
4. В файле A выбрать кластер с наибольшим числом точек, среди его оранжевых субкарликов найти ближайшего к центру и вычислить Ax и Ay.
5. В файле Б подсчитать в каждом кластере число жёлто-белых ярких гигантов, определить кластеры с минимумом и максимумом таких звёзд и найти расстояние между их центрами.
6. Среди белых ярких гигантов каждого кластера найти максимальное попарное расстояние.
2. Разбить точки на кластеры, используя условие о прямоугольниках со сторонами H=6,0 и W=5,5.
3. Для каждого кластера найти точку, минимизирующую сумму расстояний до всех остальных точек этого кластера.
4. В файле A выбрать кластер с наибольшим числом точек, среди его оранжевых субкарликов найти ближайшего к центру и вычислить Ax и Ay.
5. В файле Б подсчитать в каждом кластере число жёлто-белых ярких гигантов, определить кластеры с минимумом и максимумом таких звёзд и найти расстояние между их центрами.
6. Среди белых ярких гигантов каждого кластера найти максимальное попарное расстояние.
Частые ошибки
- Использование координат геометрического центра вместо точки-звезды, минимизирующей сумму расстояний.
- Путаница между спектральным классом и классом светимости.
- Неверное толкование обозначения белого яркого гиганта: спектральный класс A и класс светимости II.
- Округление вместо взятия целой части после умножения на 10000.
- Поиск максимального расстояния между звёздами разных кластеров при вычислении $B_2$.
Источник: Открытый банк ФИПИ
Похожие задания
27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 577EED27Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 76B8BD27Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 7B95E827Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 82E6AD27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 90EECD27Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…Кластеры точек и звёзд · 9C15B927Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.