1210 - Is it possible?
Time Limit : 1 Second
Memory Limit : 128 MB
Special Judge
Submission: 74
Solved: 13
- Description
- There are n red points and n green points on the 2D plane, and no three points lie on the same line. You are asked to draw some straight segments among these points obey the following rules:
1, A segment can be drew between two points only if the colors of the two points are different.
2, Every point must be an end point of exactly one segment.
3, Any two segments can’t have intersections.
Is it possible?
- Input
- The first line contains an integer T means the number of the test cases.
For each test case, the first line contains one integer n(1<=n<=100) . The following 2*n lines contain the 2*n points, the first n lines are the red points and the next n lines are the green points. Each point is specified by two integers x,y (-104< x,y < 104) .
- Output
- For each test case, you should output a single with “Yes” if it’s possible or else “No”. If it’s possible, please output another line contains n integers a1, a2 , …, an, and they must be separated by exactly one space. While the ith integer ai is the index of the green point, which is connected with the ith red point with a straight segment.
If there are many solutions, output any of them.
- sample input
-
2 1 0 0 1 1 2 0 0 1 1 1 0 0 1
- sample output
-
Yes 1 Yes 1 2
- hint
- source