P10097 [ROIR 2023] Colored Points (Day 1)

Translated from [ROIR 2023 D1T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。 There are $n$ points on the plane, namely $P_1,P_2,P_3,\dots,P_n$。The coordinates of the $i$-th point are $(x_i,y_i)$。 Choose two points $P_i,P_j$ ($i\ne j$)。Let $P_i$ be the starting point and $P_j$ be the ending point。**With the ending point $P_j$ as the center**, starting from the **direction** of the vector $\overrightarrow{P_iP_j}$, sort all points except $P_j$ in counterclockwise order (if angles are the same, sort by increasing distance to $P_j$)。Suppose the $t$-th point in this order is $P_k$。Then repeat the operation: let $P_j$ be the starting point and $P_k$ be the ending point, reorder in the same way, and compute the index of the new ending point。This process repeats in a loop。 In the figure below, initially $n=6,t=4,i=1,j=2$。Sort all points except $P_2$ in order, and the result is $P_3,P_5,P_1,P_6,P_4$，so the next ending point should be $P_6$，and the starting point is $P_2$。  Now $n=6,t=4,i=2,j=6$。Continue sorting by the rules. As in the lower-left figure, the result is $P_4,P_3,P_2,P_1,P_5$。So the next ending point is $P_1$，and the starting point is $P_6$。  Now $n=6,t=4,i=6,j=1$。Continue sorting by the rules. As in the upper-right figure, the result is $P_5,P_6,P_4,P_2,P_3$。So the next ending point is $P_2$，and the starting point is $P_1$。Now we return to the initial situation and enter a cycle。

We paint each of the $n$ points with one of three colors。The color of point $i$ is determined as follows： - If there exists a point $j$ such that, choosing point $i$ as the starting point and point $j$ as the ending point, in the process above point $i$ will become the starting point infinitely many times, then paint point $i$ green。 - If point $i$ is not painted green and there exists a point $j$ such that, choosing point $i$ as the starting point and point $j$ as the ending point, in the process above point $i$ can still become the starting point at least once, then paint point $i$ blue。 - If point $i$ is neither green nor blue, then paint point $i$ red。 For each point, determine which color it should be painted。

The first line contains two integers $n$ and $t$。 The next $n$ lines each contain two integers $x_i$ and $y_i$。It is guaranteed that no two points coincide。

Output one line containing $n$ characters。The $i$-th character of the string indicates the color of the $i$-th point。 Green points are denoted by the letter `G`，blue points by `B`，and red points by `R`。

Explanation for sample $1$： In the example given above, we already know that $P_1,P_2,P_6$ form a cycle. These three points will definitely be visited infinitely many times, so they should be painted green。 When the starting point is $P_3$, we can take the ending point as $P_1$。After sorting, $P_3$ is exactly the fourth point, so $P_3$ returns to being a starting point again, as shown below. Therefore it should be painted blue。  When the starting point is $P_4$, we can choose $P_5$ as the ending point. After sorting, $P_4$ is exactly the fourth point. Therefore $P_4$ can be painted blue。When $P_5$ is the starting point, it is easy to see that it can be painted neither green nor blue, so it should be painted red。 This problem uses bundled testdata。 | Subtask | Score | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $10$ | $n\le10$，all points are collinear | | $2$ | $15$ | all points are collinear | | $3$ | $10$ | $n\le10$，there are no blue points | | $4$ | $10$ | $n\le10$ | | $5$ | $15$ | $n\le100$，there are no blue points | | $6$ | $15$ | $n\le100$ | | $7$ | $5$ | $n\ge3$，all points form a strictly convex $n$-gon, and are given in counterclockwise order | | $8$ | $20$ | none | Constraints for all data: $2 \le n \le 1 000, 1 \le t \le n−1, −10^9 \le x_i, y_i \le 10^9$。 Translated by ChatGPT 5