Love Story VI

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

We all have watched the famous TV series “Princess Pearl”, and I won’t summarize the story as I think it is very nc.
One day, Yongqi and Xiaoyanzi are riding horses on the prairies. Xiaoyanzi commands Yongqi to build a fence. A closed fence in the plane is a set of non-crossing, connected line segments with N corners. The corners or vertices are each distinct and are listed in counter-clockwise order in an array {xi, yi} (1 <= I <= N). Every pair of adjacent vertices defines a side of the fence. Thus {xi, yi, xi+1, yi+1} is a side of the fence for all i in (1..N). When N+1 = 1, the first and last vertices make the fence closed. Yongqi wants to know the ordered list of vertices {xi, yi} to build a fence whether it is a valid fence. Xiaoyanzi wants to find the set of fence sides that herself (ignoring her height) who is standing in the plane at position (x, y) can "see" when looking at the fence. The location (x, y) may fall anywhere not on the fence.
A fence side can be seen if there exists a ray that connects (x, y) and any point on the side, and the ray does not intersect any other side of the fence. A side that is parallel to the line of sight is not considered visible.

Input

Input contains multiple test cases. The first line contains one integer N which is the number of corners in the fence. The second line contains two integers x and y which is the location of Xiaoyanzi. The next n lines all contains two integers x and y, that are the location of the fences. The pairs are given in counterclockwise order. Both integers are no larger than 1000 in magnitude.

Output

If the sequence is not a valid fence, the output is a single line containing the word "NC". Otherwise, the output is a listing of visible fence segments, one per line, shown as four space-separated integers that represent the two corners. Express the points in the segment by showing first the point that is earlier in the input, then the point that is later. Sort the segments for output by examining the last point and showing first those points that are earlier in the input. Use the same rule on the first of the two points in case of ties.

Sample Input

13
5 5
0 0
7 0
5 2
7 5
5 7
3 5
4 9
1 8
2 5
0 9
-2 7
0 3
-3 1 

Sample Output

7
0 0 7 0
5 2 7 5
7 5 5 7
5 7 3 5
-2 7 0 3
0 0 -3 1
0 3 -3 1

Hint

Source

方静远

提交代码