Problem J
Traffic Lights
Languages
en
is
You have landed a job at Vegagerðin (Icelandic Road Administration) with the task of recalibrating the traffic lights of Reykjavík. As is mandatory in all government positions this of course has to be done in the most inefficient manner possible.
Thus no two adjacent traffic lights may have the same colour, otherwise you could possibly drive right through two of them in a row. That would be dangerously efficient!
Furthermore, we cannot have too many traffic accidents, so each intersection has to have a green light going one way and a red light the other way, or a yellow light both ways. This of course assumes that people follow traffic laws.
The road system of Reykjavík is given as $n$ line segments where no three line segments intersect at a single point. That is to say, intersections are placed at every point where two roads meet, and there are never three or more roads that intersect at a single point. Furthermore any two roads intersect at most at a single point.
Figure out a way to set the lights at the intersections such that the conditions given above hold. Two intersections are considered adjacent if they are on the same road and there are no other intersections between them on that road.
Input
The input begins with a single positive integer $n$, the number of roads. You may assume that $n \leq 100\, 000$. Next there are $n$ lines where the $i$-th line gives the $i$-th road. The $i$-th road is given as four integers $x_1, y_1, x_2, y_2$ which means the road goes from $(x_1, y_1)$ to $(x_2, y_2)$. You may assume that $(x_1, y_1) != (x_2, y_2)$. All coordinates are at least $-1\, 000\, 000$ and at most $1\, 000\, 000$.
Output
First print the number of intersections on its own line. Then for each intersection print one line. Print L1 L2 C1 C2 on each line where $L_1$ and $L_2$ are the indices of the roads that intersect. $C_1$ denotes the colour of the traffic light at that intersection for the road $L_1$ and $C_2$ the colour for the road $L_2$. Here $C_1$ and $C_2$ are both one of the letters r, y or g. Here r denotes red, y yellow and g green. There will never be more than $200\, 000$ intersections in the output.
If there are many possible answers you may print any one of them.
Scoring
|
Group |
Points |
Constraints |
|
1 |
10 |
$n \leq 2$. |
|
2 |
20 |
$n \leq 10$. |
|
3 |
20 |
$n \leq 1\, 000$. |
|
4 |
20 |
$n \leq 100\, 000$, line segments only intersect at their endpoints. |
|
5 |
20 |
$n \leq 100\, 000$, all line segments are parallel to the coordinate axes. |
|
6 |
10 |
$n \leq 100\, 000$. |
| Sample Input 1 | Sample Output 1 |
|---|---|
5 -3 1 5 -3 5 4 2 -4 -1 -1 7 3 2 3 5 -6 -3 0 10 1 |
10 1 5 r g 1 3 y y 3 5 g r 3 4 y y 1 2 g r 4 5 r g 2 4 y y 2 5 g r 1 4 r g 2 3 r g |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 5 4 -7 -3 5 3 -7 -2 5 1 -7 2 5 -4 -7 1 5 -3 -7 -1 5 -1 -7 4 5 5 -7 0 |
14 4 7 r g 2 5 r g 1 5 g r 2 4 y y 1 4 r g 3 7 g r 6 7 r g 1 2 g r 3 6 r g 1 6 y y 2 6 g r 1 3 r g 4 5 r g 2 3 y y |
