시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 412 87 67 22.867%

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 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
W3sicHJvYmxlbV9pZCI6IjM2NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWMyMWMgXHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWJhNzQgXHVjNzA0XHVjNzU4IFx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM5ZDFcdWQ1NjlcdWM3NTggXHViYWE4XHViNGUwIFx1YzgxMFx1Yzc0MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVjOWQxXHVkNTY5XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWM4MTBcdWM3NDQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NDAgXHVjNWYwXHVjMThkXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWMxMjBcdWJkODRcdWM3NTggXHVhZDUwXHVjODEwXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWFkNTBcdWNjMjhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Nwb2x5Z29uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MnB4OyB3aWR0aDo0NDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWM4MTBcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHViYWE4XHViNGUwIFx1YzgxMFx1Yzc3NCBcdWQ1NWMgXHVjOWMxXHVjMTIwXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBjICgxICZsZTsgYyAmbGU7IDIwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuICgzICZsZTsgbiAmbGU7IDIwMDApIFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIHhcdWM2NDAgeVx1Yzc3NFx1YmE3MCwgXHVjODhjXHVkNDVjXHViMjk0IC0xMCwwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IDBcdWJkODBcdWQxMzAgbi0xXHVhZTRjXHVjOWMwIFx1YzIxY1x1YzVmNFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgxMFx1Yzc0NCBcdWM3NzRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM2MmNcdWJjMTRcdWI5NzggXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNpbXBsZSBQb2x5Z29uIiwiZGVzY3JpcHRpb24iOiI8cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjb25zdHJ1Y3RzIGEgcG9seWdvbiBmcm9tIGEgZ2l2ZW4gc2V0IG9mIHBvaW50cyBpbiB0aGUgcGxhbmUuIEVhY2ggcG9pbnQgb2YgdGhlIHNldCBoYXMgdG8gYmUgYSB2ZXJ0ZXggb2YgdGhlIHBvbHlnb24sIGFuZCB0aGUgcG9seWdvbiBtdXN0IG5vdCBoYXZlIGFueSBvdGhlciB2ZXJ0aWNlcy4gTm8gdHdvIGxpbmUgc2VnbWVudHMgb2YgdGhlIHBvbHlnb24gbWF5IGhhdmUgYW55IHBvaW50IGluIGNvbW1vbiwgZXhjZXB0IGZvciB0aGUgbWlkZGxlIHZlcnRleCBvZiB0d28gY29uc2VjdXRpdmUgbGluZSBzZWdtZW50cy4gRm9yIGV4YW1wbGUsIGdpdmVuIHRoZSBwb2ludHMgb24gdGhlIGxlZnQtaGFuZCBzaWRlLCBhIHZhbGlkIHBvbHlnb24gaXMgc2hvd24gb24gdGhlIHJpZ2h0LWhhbmQgc2lkZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zcG9seWdvbi5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTJweDsgd2lkdGg6NDQxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSB2YWxpZCBwb2x5Z29uIGlzIGd1YXJhbnRlZWQgdG8gZXhpc3QsIGFuZCBhbnkgdmFsaWQgcG9seWdvbiB3aWxsIGJlIGFjY2VwdGVkIGFzIGEgY29ycmVjdCBhbnN3ZXIuIE1vcmVvdmVyLCBubyB0d28gcG9pbnRzIHdpbGwgc2hhcmUgdGhlIHNhbWUgbG9jYXRpb24sIGFuZCBub3QgYWxsIHBvaW50cyB3aWxsIGJlIGNvbGxpbmVhci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBjICgxICZsZTsgYyAmbGU7IDIwMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBmb2xsb3cgdGhlIHRlc3QgY2FzZXMsIG9uZSBwZXIgbGluZS48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYW4gaW50ZWdlciBuICgzICZsZTsgbiAmbGU7IDIgMDAwKSwgdGhlIG51bWJlciBvZiBnaXZlbiBwb2ludHMuIFRoZW4gZm9sbG93LCBvbiB0aGUgc2FtZSBsaW5lLCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBvaW50cy4gRWFjaCBwb2ludCBpcyBzcGVjaWZpZWQgYnkgdHdvIGludGVnZXJzIHggYW5kIHkgaW4gdGhlIHJhbmdlIC0xMCAwMDAgdG8gMTAgMDAwLCBpbmNsdXNpdmVseS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHBlcm11dGF0aW9uIG9mIHRoZSBudW1iZXJzIDAgdG8gbi0xLiBFYWNoIG9mIHRoZXNlIG51bWJlcnMgcmVwcmVzZW50cyB0aGUgaW5kZXggb2YgYSBwb2ludCwgaW4gdGhlIHNhbWUgb3JkZXIgYXMgZ2l2ZW4gaW4gdGhlIGlucHV0LiBXaGVuIGRyYXdpbmcgbGluZSBzZWdtZW50cyBiZXR3ZWVuIGNvbnNlY3V0aXZlIHBvaW50cyBpbiB0aGUgb3JkZXIgZ2l2ZW4gYnkgdGhpcyBwZXJtdXRhdGlvbiwgdGhlIHJlc3VsdCBtdXN0IGJlIGEgdmFsaWQgcG9seWdvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=