Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Разноцветные точки

(Время: 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.TXTOUTPUT.TXT
16 4
-1 -1
1 -2
4 -2
2 -4
2 3
-4 -5
GGBBRG
22 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

Во втором примере из условия легко показать, что если одна из точек является начальной, а другая – следующей, то прицельной станет точка, которая являлась начальной. Поэтому обе точки будут окрашены в зеленый цвет.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Разделение прямоугольника
 B. Произведение Фибоначчи
 C. Робот-пылесос
 D. Разноцветные точки
 E. Метрострой
 F. Красивые последовательности
 G. Камни
 H. Обыкновенная задача про строки

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru