Задание 27 ЕГЭ по информатике · 7B95E8
Кластеры точек и звёздВысокаяКЭС 4.1
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной H=6,0 и W=5,5, причём прямоугольники не пересекались. Стороны прямоугольников не обязательно параллельны координатным осям. Такое разбиение существует и единственно.
Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных точек минимальна. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют цветам: голубой, бело-голубой, белый, жёлто-белый, жёлтый, оранжевый, красный. Каждый спектральный класс имеет подклассы от 0 до 9. Класс светимости обозначается римскими цифрами от I до VII: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.
В файле A содержится информация о точках двух кластеров, а в файле Б — о точках трёх кластеров. В каждой строке записаны координаты звезды и её спектральный класс, подкласс и класс светимости. Для белых карликов класса VII спектральный класс и подкласс не указываются. Количество точек в файле A не превышает 2000, а в файле Б — 10 000.
Для файла A определите координаты центров кластеров, затем найдите A1 — количество жёлтых субгигантов, расположенных на расстоянии не более 1,2 от центра кластера с наименьшим количеством точек, и A2 — расстояние между центрами кластеров.
Для файла Б определите координаты центров кластеров, затем найдите B1 — наибольшее расстояние от центра кластера до оранжевого гиганта, принадлежащего этому кластеру, и B2 — наибольшее количество белых ярких гигантов в одном кластере.
Для выполнения задания используйте данные из прилагаемых файлов.
1_7B95E8.zipЦентром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных точек минимальна. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют цветам: голубой, бело-голубой, белый, жёлто-белый, жёлтый, оранжевый, красный. Каждый спектральный класс имеет подклассы от 0 до 9. Класс светимости обозначается римскими цифрами от I до VII: сверхгигант, яркий гигант, гигант, субгигант, карлик, субкарлик, белый карлик.
В файле A содержится информация о точках двух кластеров, а в файле Б — о точках трёх кластеров. В каждой строке записаны координаты звезды и её спектральный класс, подкласс и класс светимости. Для белых карликов класса VII спектральный класс и подкласс не указываются. Количество точек в файле A не превышает 2000, а в файле Б — 10 000.
Для файла A определите координаты центров кластеров, затем найдите A1 — количество жёлтых субгигантов, расположенных на расстоянии не более 1,2 от центра кластера с наименьшим количеством точек, и A2 — расстояние между центрами кластеров.
Для файла Б определите координаты центров кластеров, затем найдите B1 — наибольшее расстояние от центра кластера до оранжевого гиганта, принадлежащего этому кластеру, и B2 — наибольшее количество белых ярких гигантов в одном кластере.
Для выполнения задания используйте данные из прилагаемых файлов.
Показать ответ
14 129272; 22689 21
Подсказки (3)
- Сначала восстановите кластеры по геометрическому условию, перебирая точки и проверяя, могут ли они принадлежать одному прямоугольнику со сторонами H и W.
- Для каждого найденного кластера вычислите для каждой точки сумму расстояний до всех остальных точек. Точка с минимальной суммой является центром кластера.
- После нахождения центров посчитайте требуемые характеристики звёзд и расстояния. В ответ запишите A1 и целую часть A2⋅10000 в первой строке, затем целую часть B1⋅10000 и B2 во второй.
Решение
1. Считать координаты и характеристики всех звёзд из файлов A и Б.
2. Разбить точки каждого файла на кластеры. Для каждой группы необходимо проверить, что все её точки можно разместить внутри прямоугольника со сторонами 6,0 и 5,5, допускающего произвольный поворот, и что прямоугольники разных кластеров не пересекаются.
3. Для каждого кластера для каждой точки вычислить сумму расстояний до всех остальных точек: Si=∑j≠id(Pi,Pj). Точка с минимальным значением Si является центром.
4. В файле A выбрать кластер с минимальным числом точек. Подсчитать в нём жёлтые субгиганты, то есть звёзды спектрального класса G любого подкласса и класса светимости IV, находящиеся на расстоянии не более 1,2 от центра. Это значение равно A1.
5. Вычислить расстояние между двумя центрами файла A по формуле A2= и взять целую часть числа A2⋅10000.
6. В файле Б для каждого кластера найти расстояния от его центра до всех оранжевых гигантов, то есть звёзд спектрального класса K любого подкласса и класса светимости III. Максимальное расстояние равно B1.
7. Для каждого кластера подсчитать белых ярких гигантов — звёзд класса светимости II. Максимальное из полученных количеств равно B2.
2. Разбить точки каждого файла на кластеры. Для каждой группы необходимо проверить, что все её точки можно разместить внутри прямоугольника со сторонами 6,0 и 5,5, допускающего произвольный поворот, и что прямоугольники разных кластеров не пересекаются.
3. Для каждого кластера для каждой точки вычислить сумму расстояний до всех остальных точек: Si=∑j≠id(Pi,Pj). Точка с минимальным значением Si является центром.
4. В файле A выбрать кластер с минимальным числом точек. Подсчитать в нём жёлтые субгиганты, то есть звёзды спектрального класса G любого подкласса и класса светимости IV, находящиеся на расстоянии не более 1,2 от центра. Это значение равно A1.
5. Вычислить расстояние между двумя центрами файла A по формуле A2= и взять целую часть числа A2⋅10000.
6. В файле Б для каждого кластера найти расстояния от его центра до всех оранжевых гигантов, то есть звёзд спектрального класса K любого подкласса и класса светимости III. Максимальное расстояние равно B1.
7. Для каждого кластера подсчитать белых ярких гигантов — звёзд класса светимости II. Максимальное из полученных количеств равно B2.
Частые ошибки
- Путать спектральный класс $G$ жёлтых звёзд с классом светимости.
- Путать оранжевые звёзды класса $K$ с жёлтыми звёздами класса $G$.
- Считать центром среднее арифметическое координат вместо точки с минимальной суммой расстояний.
- Забывать взять целую часть произведений $A_2\cdot10000$ и $B_1\cdot10000$.
Источник: Открытый банк ФИПИ
Похожие задания
27Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 0D9B7C27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 577EED27Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 76B8BD27Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 82E6AD27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 90EECD27Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…Кластеры точек и звёзд · 9C15B927Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.