시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 317 68 53 22.944%

문제

평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭지점이어야 하고, 집합에 없는 점을 다각형의 꼭지점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.

예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.

항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.

입력

첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌표 x와 y이며, 좌표는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

각 테스트 케이스마다 0부터 n-1까지 순열중 하나를 출력해야 한다. 출력하는 순열은 입력으로 주어지는 점의 번호를 나타내며, 출력하는 순서대로 점을 이었을 때, 올바른 다각형을 만들어야 한다.

예제 입력 1

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

예제 출력 1

0 3 1 2
3 1 2 4 0
W3sicHJvYmxlbV9pZCI6IjM2NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWMyMWMgXHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWJhNzQgXHVjNzA0XHVjNzU4IFx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM5ZDFcdWQ1NjlcdWM3NTggXHViYWE4XHViNGUwIFx1YzgxMFx1Yzc0MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVjOWQxXHVkNTY5XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWM4MTBcdWM3NDQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NDAgXHVjNWYwXHVjMThkXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NTggXHVhZDUwXHVjODEwXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWFkNTBcdWNjMjhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Nwb2x5Z29uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MnB4OyB3aWR0aDo0NDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHViNDUwIFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHVjNzNjXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVjODEwXHVjNzc0IFx1ZDU1YyBcdWM5YzFcdWMxMjBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IGMgKDEgJmxlOyBjICZsZTsgMjAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IG4gKDMgJmxlOyBuICZsZTsgMjAwMCkgXHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgeFx1YzY0MCB5XHVjNzc0XHViYTcwLCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwLDAwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgMFx1YmQ4MFx1ZDEzMCBuLTFcdWFlNGNcdWM5YzAgXHVjMjFjXHVjNWY0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODEwXHVjNzQ0IFx1Yzc3NFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2ltcGxlIFBvbHlnb24iLCJkZXNjcmlwdGlvbiI6IjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbnN0cnVjdHMgYSBwb2x5Z29uIGZyb20gYSBnaXZlbiBzZXQgb2YgcG9pbnRzIGluIHRoZSBwbGFuZS4gRWFjaCBwb2ludCBvZiB0aGUgc2V0IGhhcyB0byBiZSBhIHZlcnRleCBvZiB0aGUgcG9seWdvbiwgYW5kIHRoZSBwb2x5Z29uIG11c3Qgbm90IGhhdmUgYW55IG90aGVyIHZlcnRpY2VzLiBObyB0d28gbGluZSBzZWdtZW50cyBvZiB0aGUgcG9seWdvbiBtYXkgaGF2ZSBhbnkgcG9pbnQgaW4gY29tbW9uLCBleGNlcHQgZm9yIHRoZSBtaWRkbGUgdmVydGV4IG9mIHR3byBjb25zZWN1dGl2ZSBsaW5lIHNlZ21lbnRzLiBGb3IgZXhhbXBsZSwgZ2l2ZW4gdGhlIHBvaW50cyBvbiB0aGUgbGVmdC1oYW5kIHNpZGUsIGEgdmFsaWQgcG9seWdvbiBpcyBzaG93biBvbiB0aGUgcmlnaHQtaGFuZCBzaWRlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Nwb2x5Z29uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MnB4OyB3aWR0aDo0NDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIHZhbGlkIHBvbHlnb24gaXMgZ3VhcmFudGVlZCB0byBleGlzdCwgYW5kIGFueSB2YWxpZCBwb2x5Z29uIHdpbGwgYmUgYWNjZXB0ZWQgYXMgYSBjb3JyZWN0IGFuc3dlci4gTW9yZW92ZXIsIG5vIHR3byBwb2ludHMgd2lsbCBzaGFyZSB0aGUgc2FtZSBsb2NhdGlvbiwgYW5kIG5vdCBhbGwgcG9pbnRzIHdpbGwgYmUgY29sbGluZWFyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIGMgKDEgJmxlOyBjICZsZTsgMjAwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGVuIGZvbGxvdyB0aGUgdGVzdCBjYXNlcywgb25lIHBlciBsaW5lLjxcL3A+XHJcblxyXG48cD5FYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4gKDMgJmxlOyBuICZsZTsgMiAwMDApLCB0aGUgbnVtYmVyIG9mIGdpdmVuIHBvaW50cy4gVGhlbiBmb2xsb3csIG9uIHRoZSBzYW1lIGxpbmUsIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzLiBFYWNoIHBvaW50IGlzIHNwZWNpZmllZCBieSB0d28gaW50ZWdlcnMgeCBhbmQgeSBpbiB0aGUgcmFuZ2UgLTEwIDAwMCB0byAxMCAwMDAsIGluY2x1c2l2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgcGVybXV0YXRpb24gb2YgdGhlIG51bWJlcnMgMCB0byBuLTEuIEVhY2ggb2YgdGhlc2UgbnVtYmVycyByZXByZXNlbnRzIHRoZSBpbmRleCBvZiBhIHBvaW50LCBpbiB0aGUgc2FtZSBvcmRlciBhcyBnaXZlbiBpbiB0aGUgaW5wdXQuIFdoZW4gZHJhd2luZyBsaW5lIHNlZ21lbnRzIGJldHdlZW4gY29uc2VjdXRpdmUgcG9pbnRzIGluIHRoZSBvcmRlciBnaXZlbiBieSB0aGlzIHBlcm11dGF0aW9uLCB0aGUgcmVzdWx0IG11c3QgYmUgYSB2YWxpZCBwb2x5Z29uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==