A Simple Polygon
All submissions for this problem are available.
You are given a simple (not self-intersecting polygon, without holes) polygon P with N vertices. You have to find 500 pairs of vertices such that the line segments joining these two points lie completely inside the polygon (i.e. suppose AB is a segment, then it should be inside the polygon and it shouldn't touch or intersect the polygon at any other point than A or B). None of the line segments made by these vertices should be one of the sides of the polygon. In a pair, the two vertices should be different. Along with this, none of the 500 line segments should be intersecting with each other at a point other than the endpoints. That is, if there is a selected line segment between the vertices A and B, and another selected line segment between the vertices C and D, the only points where they can touch are at A, B, C, or D.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the number of vertices of the polygon P.
Each of the next N lines contain two space separated integers denoting the x and y coordinates of the i-th vertex of the polygon P. It's guaranteed that no three consecutive vertices of the polygon are collinear. The polygons can be in any of the clockwise or counter-clockwise order.
For each test case, output 500 lines each containing two integers which should be the indices (1-based) of a pair of vertices. You can output the indices in any order. If there are multiple possible such segments, you can output any. Note that each of these line segments should be distinct, i.e. no line segment should appear more than once in the output.
- 1 ≤ T ≤ 400
- 103 ≤ N ≤ 5 * 104
- -109 ≤ x, y ≤ 109
- Sum of N over all the test cases in a single file would be at most 2 * 105
Input 2 4 0 0 1 0 1 1 0 1 4 -1 0 0 0 0 1 2 -1 Output 1 3 4 2
Please note the samples provided are wrong. They are for representative purposes only. These samples are provided assuming that you just print only 1 line segment. Also, the samples don't follow the constraints of N, which will be followed in the actual input.
Testcase 2: The figure below shows the polygon in the input, with the vertices marked as 1, 2, 3 and 4. The output given is the line segment between vertices 2 and 4, which is also shown in the figure.
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.