Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Simple Polygon
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 703Accepted: 221Special Judge

Description

Write a program that constructs a polygon from a given set of points in the plane. 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:

A valid polygon is guaranteed to exist, and any valid polygon will be accepted as a correct answer. Moreover, no two points will share the same location, and not all points will be collinear.

Input

The first line of the input consists of an integer c (1 <= c <= 200), the number of test cases. Then follow the test cases, one per line.
Each test case starts with an integer n (3 <= n <= 2 000), the number of given points. Then follow, on the same line, the coordinates of the points. Each point is specified by two integers x and y in the range -10 000 to 10 000, inclusively.

Output

For each test case, print a single line containing 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.

Sample Input

2
4 0 0 2 0 0 1 1 0
5 0 0 10 0 10 5 5 -1 0 5

Sample Output

0 3 1 2
3 1 2 4 0

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator