Задание выполняется с использованием прилагаемого файла.

Астроном решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба.

Область наблюдения представляет собой круг с центром в точке (0, 0).

Кластер звёзд — это набор звёзд (точек) на графике, лежащий внутри сектора этого круга с углом α.

Каждая звезда обязательно принадлежит только одному из кластеров.

Гарантируется, что такое разбиение существует и единственно для заданного α.

Внимание!

График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию: на нём показаны два кластера, а в файле их три, и угол α на графике другой.

Точки отложены в декартовой системе координат.

Для выполнения задания используйте данные из прилагаемого файла.

Истинный центр кластера, или центроид, — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна.

В каждой строке текстового файла хранится информация об одной звезде: сначала полярный угол φ в градусах, затем полярный радиус r в условных единицах, затем спектральный класс, обозначаемый одной из латинских букв O, B, A, F, G, K, M.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.

Количество строк в файле не превышает 10 000.

Полярный угол не превосходит 360,0, полярный радиус не превосходит 100,0.

Известно, что все описанные в файле звёзды подразделяются ровно на 3 кластера (N = 3) с α = 20 градусов для каждого.

Для каждого кластера определите его центроид, затем найдите два числа: Q1 — наибольшее расстояние от центроида кластера до звезды этого же кластера, имеющей спектральный класс G, и Q2 — наибольшее расстояние от начала координат до центроида кластера.

Оба числа берутся как наибольшие по всем кластерам.

В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

Для справки

Декартовы координаты точки, заданной полярным углом φ (в градусах) и полярным радиусом r, вычисляются по формулам:

x = r cos((π φ)/(180)), y = r sin((π φ)/(180)).

Евклидово расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

d(A, B) = √((x2 - x1)² + (y2 - y1)²).

Типовой пример организации данных во входном файле Три строки файла для трёх звёзд:

45,000000	10,000000  G
120,000000  8,500000   M
7,250000	95,004500  B

Для звезды из первой строки примера декартовы координаты равны (7,0711; 7,0711).

Типовой пример имеет иллюстративный характер.

Для выполнения задания используйте данные из прилагаемого файла.