Задание 27 ЕГЭ по информатике · 577EED
Кластеры точек и звёздВысокаяКЭС 4.1
Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждой точки центра гарантируется единственность. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют голубому, бело-голубому, белому, жёлто-белому, жёлтому, оранжевому и красному цветам. Каждый спектральный класс делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса, например B2.
Классы светимости обозначаются римскими цифрами от 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. Структура хранения информации аналогична структуре файла А.
Для файла А определите координаты центра каждого кластера, затем найдите A1 — количество бело-голубых ярких гигантов, расположенных на расстоянии не более 1,5 от центра кластера, содержащего наименьшее количество точек, и A2 — расстояние между центрами кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите B1 — наибольшее расстояние от центра кластера до жёлтого карлика, принадлежащего этому кластеру, и B2 — наибольшее количество оранжевых карликов в одном кластере.
В ответе запишите четыре числа: в первой строке сначала A1, затем целую часть произведения A2⋅10000; во второй строке сначала целую часть произведения B1⋅10000, затем B2.
Пример организации данных в одном из исходных файлов для случая четырёх звёзд:
5,01788 8,32466 G2V
4,289251 6,955186 VII
4,619358 5,524697 B7V
6,91934 20,425391 G2V
Пример приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
1_577EED.zipФрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Центром кластера называется точка этого кластера, сумма расстояний от которой до всех остальных его точек минимальна. Для каждой точки центра гарантируется единственность. Расстояние между точками A(x1,y1) и B(x2,y2) вычисляется по формуле d(A,B)=.
Каждая звезда характеризуется спектральным классом и классом светимости. Спектральные классы O, B, A, F, G, K, M соответствуют голубому, бело-голубому, белому, жёлто-белому, жёлтому, оранжевому и красному цветам. Каждый спектральный класс делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса, например B2.
Классы светимости обозначаются римскими цифрами от 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. Структура хранения информации аналогична структуре файла А.
Для файла А определите координаты центра каждого кластера, затем найдите A1 — количество бело-голубых ярких гигантов, расположенных на расстоянии не более 1,5 от центра кластера, содержащего наименьшее количество точек, и A2 — расстояние между центрами кластеров.
Для файла Б определите координаты центра каждого кластера, затем найдите B1 — наибольшее расстояние от центра кластера до жёлтого карлика, принадлежащего этому кластеру, и B2 — наибольшее количество оранжевых карликов в одном кластере.
В ответе запишите четыре числа: в первой строке сначала A1, затем целую часть произведения A2⋅10000; во второй строке сначала целую часть произведения B1⋅10000, затем B2.
Пример организации данных в одном из исходных файлов для случая четырёх звёзд:
5,01788 8,32466 G2V
4,289251 6,955186 VII
4,619358 5,524697 B7V
6,91934 20,425391 G2V
Пример приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Показать ответ
7 128336; 7 99562
Подсказки (3)
- Сначала прочитайте координаты и классификацию звёзд из файлов, затем найдите кластеры по условию о непересекающихся прямоугольниках.
- Для каждого кластера вычислите для каждой точки сумму расстояний до остальных точек и выберите точку с минимальной суммой.
- После нахождения центров отфильтруйте звёзды по спектральному классу и классу светимости, вычислите расстояния до соответствующих центров и выполните требуемые подсчёты.
Решение
1. Прочитать файлы и сохранить для каждой звезды координаты, спектральный класс, подкласс и класс светимости. Для белых карликов спектральные данные отсутствуют.
2. Разбить точки на кластеры. Так как размеры ограничивающих прямоугольников равны H=6,0 и W=5,5, точки одного кластера должны помещаться в одном таком прямоугольнике, а прямоугольники разных кластеров не должны пересекаться.
3. Для каждого найденного кластера перебрать все его точки и вычислить сумму расстояний от каждой точки до остальных по формуле d=. Точка с минимальной суммой является центром кластера.
4. Для файла A выбрать кластер с наименьшим числом точек. В нём посчитать бело-голубые яркие гиганты, то есть звёзды класса B с любым подклассом и классом светимости II, на расстоянии не более 1,5 от центра. Это значение равно A1.
5. Для файла A вычислить расстояние между двумя центрами и взять целую часть произведения A2⋅10000.
6. Для файла Б в каждом кластере найти жёлтые карлики, то есть звёзды класса G с классом светимости V, и вычислить расстояние от каждой такой звезды до центра её кластера. Максимальное расстояние равно B1.
7. Для файла Б в каждом кластере посчитать оранжевых карликов, то есть звёзды класса K с классом светимости V. Максимальное из полученных количеств равно B2.
8. Записать четыре полученных целых числа в требуемом порядке.
2. Разбить точки на кластеры. Так как размеры ограничивающих прямоугольников равны H=6,0 и W=5,5, точки одного кластера должны помещаться в одном таком прямоугольнике, а прямоугольники разных кластеров не должны пересекаться.
3. Для каждого найденного кластера перебрать все его точки и вычислить сумму расстояний от каждой точки до остальных по формуле d=. Точка с минимальной суммой является центром кластера.
4. Для файла A выбрать кластер с наименьшим числом точек. В нём посчитать бело-голубые яркие гиганты, то есть звёзды класса B с любым подклассом и классом светимости II, на расстоянии не более 1,5 от центра. Это значение равно A1.
5. Для файла A вычислить расстояние между двумя центрами и взять целую часть произведения A2⋅10000.
6. Для файла Б в каждом кластере найти жёлтые карлики, то есть звёзды класса G с классом светимости V, и вычислить расстояние от каждой такой звезды до центра её кластера. Максимальное расстояние равно B1.
7. Для файла Б в каждом кластере посчитать оранжевых карликов, то есть звёзды класса K с классом светимости V. Максимальное из полученных количеств равно B2.
8. Записать четыре полученных целых числа в требуемом порядке.
Частые ошибки
- Используют среднее арифметическое координат вместо точки кластера с минимальной суммой расстояний.
- Путают спектральный класс $B$ с классом светимости $II$.
- Считают бело-голубыми звёзды класса $A$, хотя бело-голубой цвет соответствует классу $B$.
- Для жёлтых звёзд используют класс $K$ вместо класса $G$.
- Забывают умножить расстояния на 10000 перед взятием целой части.
- Включают белых карликов в подсчёт звёзд с заданным спектральным классом.
Источник: Открытый банк ФИПИ
Похожие задания
27Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 0D9B7C27Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 76B8BD27Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера…Кластеры точек и звёзд · 7B95E827Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 82E6AD27Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · 90EECD27Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…Кластеры точек и звёзд · 9C15B927Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.