Задание 27 ЕГЭ по информатике · EAFDD5
Кластеры точек и звёздВысокаяКЭС 4.1
Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек-звёзд на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной 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. В файле Б содержится информация о точках трёх кластеров при H=6,0 и W=5,5. Количество точек в файле A не превышает 2000, а в файле Б — 10 000. Для звёзд классов светимости I–VI после координат записаны спектральный класс, подкласс и класс светимости без разделителей. Для белых карликов класса VII спектральный класс и подкласс не указываются.
Для файла A определите координаты центров двух кластеров, затем найдите абсциссу Ax и ординату Ay красного гиганта, ближайшего к центру кластера с наименьшим количеством точек.
Для файла Б определите координаты центров трёх кластеров, затем найдите B1 — расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов, и B2 — наибольшее расстояние между жёлтыми карликами одного кластера.
В ответе запишите четыре числа: в первой строке — целую часть абсолютной величины произведения Ax×10000, затем целую часть абсолютной величины произведения Ay×10000; во второй строке — целую часть произведения B1×10000, затем целую часть произведения B2×10000. Для решения используйте данные из прилагаемых файлов.
1_EAFDD5.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. В файле Б содержится информация о точках трёх кластеров при H=6,0 и W=5,5. Количество точек в файле A не превышает 2000, а в файле Б — 10 000. Для звёзд классов светимости I–VI после координат записаны спектральный класс, подкласс и класс светимости без разделителей. Для белых карликов класса VII спектральный класс и подкласс не указываются.
Для файла A определите координаты центров двух кластеров, затем найдите абсциссу Ax и ординату Ay красного гиганта, ближайшего к центру кластера с наименьшим количеством точек.
Для файла Б определите координаты центров трёх кластеров, затем найдите B1 — расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов, и B2 — наибольшее расстояние между жёлтыми карликами одного кластера.
В ответе запишите четыре числа: в первой строке — целую часть абсолютной величины произведения Ax×10000, затем целую часть абсолютной величины произведения Ay×10000; во второй строке — целую часть произведения B1×10000, затем целую часть произведения B2×10000. Для решения используйте данные из прилагаемых файлов.
Показать ответ
44694 69754; 118148 253180
Подсказки (3)
- Сначала прочитайте координаты и характеристики звёзд из файлов, затем разделите точки на кластеры с помощью перебора прямоугольников размеров 6,0×5,5.
- Для каждого найденного кластера вычислите сумму расстояний от каждой его точки до остальных точек и выберите точку с минимальной суммой.
- Отдельно подсчитайте звёзды нужных типов: красные гиганты имеют спектральный класс M и класс светимости III, оранжевые гиганты — KIII, жёлтые карлики — GV. После этого выполните указанные операции с координатами и умножьте результаты на 10000.
Решение
1. Прочитать оба файла, сохранив координаты звёзд и их классы. Для белых карликов учитывать, что в записи присутствует только обозначение VII.
2. Найти единственное разбиение точек на кластеры, заключённые в непересекающиеся прямоугольники размеров 6,0×5,5.
3. Для каждого кластера определить центр как точку, минимизирующую сумму евклидовых расстояний до остальных точек кластера.
4. В файле A выбрать кластер с наименьшим числом точек, найти ближайшую к его центру звезду класса MIII и получить её координаты Ax и Ay.
5. В файле Б подсчитать в каждом кластере количество звёзд класса KIII, вычислить расстояние между центрами кластеров с минимальным и максимальным количеством таких звёзд, а также найти максимальное расстояние между двумя звёздами класса GV внутри одного кластера.
6. Вычислить целые части величин ∣Ax∣×10000, ∣Ay∣×10000, B1×10000 и B2×10000.
2. Найти единственное разбиение точек на кластеры, заключённые в непересекающиеся прямоугольники размеров 6,0×5,5.
3. Для каждого кластера определить центр как точку, минимизирующую сумму евклидовых расстояний до остальных точек кластера.
4. В файле A выбрать кластер с наименьшим числом точек, найти ближайшую к его центру звезду класса MIII и получить её координаты Ax и Ay.
5. В файле Б подсчитать в каждом кластере количество звёзд класса KIII, вычислить расстояние между центрами кластеров с минимальным и максимальным количеством таких звёзд, а также найти максимальное расстояние между двумя звёздами класса GV внутри одного кластера.
6. Вычислить целые части величин ∣Ax∣×10000, ∣Ay∣×10000, B1×10000 и B2×10000.
Частые ошибки
- Считать центром среднее арифметическое координат, хотя по условию центр является одной из точек кластера.
- Перепутать красных гигантов $MIII$ с другими звёздами спектрального класса $M$.
- Подсчитывать всех оранжевых звёзд вместо оранжевых гигантов $KIII$.
- Искать расстояние между жёлтыми карликами из разных кластеров.
- Не брать целую часть после умножения результата на $10000$.
Источник: Открытый банк ФИПИ
Похожие задания
27Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 9C8C8627Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с…Кластеры точек и звёзд · AEB8BB27Задание выполняется с использованием прилагаемых файлов. В файлах A и Б записаны координаты точек на…Кластеры точек и звёзд · B5FB7227Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · C2234527Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 0B12A6
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.