|
Разноцветные точки
(Время: 3 сек. Память: 512 Мб Сложность: 69%)
Рассмотрим n точек на плоскости, пронумерованных от 1 до n, обозначим их как P1, P2, ..., Pn, координаты i-й точки (xi, yi).
Рассмотрим следующий процесс. Выберем номер начальной точки i и номер следующей за ней точки j (i ≠ j), а также целое число t. После этого номер прицельной точки k вычисляется по следующему алгоритму. Рассмотрим вектор PiPj , направленный из точки Pi в точку Pj . Упорядочим
все точки, кроме j-й, по углу, отсчитывая против часовой стрелки от направления вектора, равного PiPj, отложенного из точки j. При равенстве угла будем упорядочивать точки по возрастанию расстояния до точки j. В качестве точки k выбирается точка, являющаяся t-й в данном порядке
при нумерации с единицы. Далее точка j становится начальной, а точка k – следующей за ней, после чего, пользуясь тем же алгоритмом, вычисляется номер прицельной точки. Этот процесс повторяется до бесконечности.
Для лучшего понимания процесса рассмотрим следующий пример. Пусть имеются 6 точек, изображенных на рисунке 1, а t = 4. Пусть номер начальной точки равен 1, а номер следующей за ней точки равен 2. Отложим вектор P1P2 от точки P2 и отсортируем все точки, кроме точки P2, по углу, отсчитывая против часовой стрелки от направления данного вектора. На рисунке 2 отложенный вектор обозначен пунктирной линией, а также для удобства проведены векторы из точки P2 во все остальные точки.
Рисунок 1: Пример множества из 6 точек
|
Рисунок 2: Вектор P1P2, а также векторы из точки P2 во все остальные точки
|
Точки будут упорядочены следующим образом: P3, P5, P1, P6, P4. Таким образом, номер прицельной точки равен 6. Далее точка 2 становится начальной, а точка 6 – следующей.
На рисунке 3 изображен процесс для начальной точки 2 и следующей точки 6. Точки будут упорядочены следующим образом: P4, P3, P2, P1, P5. Обратите внимание, что точка P1 в этом списке находится раньше, чем точка P5, так как расстояние от точки P1 до точки P6 меньше, чем расстояние от точки P5 до точки P6. Прицельная точка будет иметь номер 1.
На рисунке 4 изображен процесс для начальной точки 6 и следующей точки 1. Обратите внимание, что в данном случае вектор P6P1, отложенный из точки P1 совпадает с вектором P1P5, отложенным из точки P1. Эти векторы изображены сплошной линией. Точки будут упорядочены следующим образом: P5, P6, P4, P2, P3. Прицельная точка будет иметь номер 2. Таким образом, далее процесс начнется для начальной точки 1 и следующей точки 2 и зациклится.
Рисунок 3: Процесс для начальной точки 2
и следующей точки 6
|
Рисунок 4: Процесс для начальной точки 6
и следующей точки 1
|
Покрасим каждую из n точек в один из трех цветов. Цвет i-й точки определяется следующим образом:
- Пусть существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной бесконечное количество раз. В этом случае точка i будет покрашена в зеленый цвет.
- Пусть точка i не была покрашена в зеленый цвет и существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной еще хотя бы один раз. В этом случае точка i будет покрашена в синий цвет.
- Пусть точка i не была покрашена ни в зеленый, ни в синий цвет. В этом случае точка i будет покрашена в красный цвет.
Для каждой точки определите, в какой цвет ее нужно покрасить.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и t (2 ≤ n ≤ 1 000, 1 ≤ t ≤ n-1).
Каждая из следующих n строк содержит два целых числа xi и yi (-109 ≤ xi, yi ≤ 109). Гарантируется, что никакие две точки не совпадают.
Выходные данные
В выходной файл OUTPUT.TXT выведите строку, состоящую из n символов: i-й символ строки должен обозначать цвет i-й точки.
Для зеленой точки выведите букву «G», для синей точки – букву «B», а для красной точки – букву «R».
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 4
-1 -1
1 -2
4 -2
2 -4
2 3
-4 -5 | GGBBRG |
| 2 | 2 1
1 1
2 2 | GG |
Пояснение к примерам
Рассмотрим некоторые точки из первого примера.
Точка P1 окрашены в зеленый цвет, потому что можно выбрать точку P2 в качестве следующей, и процесс посетит точку P1 бесконечное количество раз. Данный пример был рассмотрен выше в условии задачи.
Можно показать, что точка P3 не является зеленой, однако она является синей, так как можно выбрать точку 1 в качестве следующей, точка 3 окажется начальной еще хотя бы один раз. Процесс для начальной точки 1 и следующей точки 3 проиллюстрирован на рисунках 5, 6 и 7 ниже.
Для начальной точки 3 и следующей точки 1 точки будут упорядочены следующим образом: P6, P4, P2, P3, P5. Точка с номером 3 становится прицельной. Далее для начальной точки 1 и следующей точки 3 точки будут упорядочены следующим образом: P5, P1, P2, P6, P4. Точка с номером 6 становится прицельной. Наконец, для начальной точки 3 и следующей точки 6 точки будут упорядочены следующим образом: P4, P3, P2, P1, P5. Точка с номером 1 становится прицельной. Далее процесс продолжится с начальной точкой 6 и следующей точкой 1. Из примера, описанного выше в условии задачи, мы знаем, что процесс зациклится, посещая точки с номерами 6, 1 и 2.
Рисунок 5: Процесс для начальной точки 3
и следующей точки 1
|
Рисунок 6: Процесс для начальной точки 1
и следующей точки 3
|
Рисунок 7: Процесс для начальной точки 3
и следующей точки 6
Во втором примере из условия легко показать, что если одна из точек является начальной, а другая – следующей, то прицельной станет точка, которая являлась начальной. Поэтому обе точки будут окрашены в зеленый цвет.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
