Server Time: Mon Jul 6, 2020 12:01 am
Welcome ( logout
1285 - Drawing Simple Polygon
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Given set of points in the plane, your task is to draw a polygon using the points. You have to use all the points. To be more specific, each point of the set has to be a vertex of the polygon, and the polygon must not have any other vertices. No two line segments of the polygon may have any point in common, except for the middle vertex of two consecutive line segments. For example, given the points on the left-hand side, a valid polygon is shown on the right-hand side:

You can assume that, no two points will share the same location.


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (3 ≤ n ≤ 2000), denoting the number of points. The next line contains the co-ordinates of the points. Each point is specified by two integer x y in the range [-104, 104].


For each case, print the case number in a single line first. In the next line print 'Impossible' if no solution can be found. Otherwise print a permutation of the numbers 0 to n-1. Each of these numbers represents the index of a point, in the same order as given in the input. When drawing line segments between consecutive points in the order given by this permutation, the result must be a valid polygon. Insert a single space between two integers.

Sample Input

Output for Sample Input



0 0 2 0 0 1 1 0


0 0 10 0 10 5 5 -1 0 5

Case 1:

0 3 1 2

Case 2:

2 1 3 0 4


This is a special judge problem; wrong output format may cause 'wrong answer'.

Problem Setter: Sabbir Yousuf Sanny
Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan