시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB224371713.492%

문제

공선점 (Collinear Points)은 한 직선 상에 있는 점의 집합을 말한다. 이와 비슷한게 공원점(Cocircular Points)을 한 원 위에 있는 점의 집합으로 정의할 수 있다.

점의 집합이 주어졌을 때, 이 집합의 부분 집합 중 크기가 가장 큰 공원점을 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 점의 좌표 X와 Y가 주어진다. (-104 ≤ X,Y ≤ 104) 두 점의 좌표가 같은 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해, 입력으로 주어진 집합의 부분 집합 중 크기가 가장 큰 공원점의 크기를 출력한다.

예제 입력 1

7
-10 0
0 -10
10 0
0 10
-20 10
-10 20
-2 4
4
-10000 10000
10000 10000
10000 -10000
-10000 -9999
3
-1 0
0 0
1 0
0

예제 출력 1

5
3
2
W3sicHJvYmxlbV9pZCI6IjU2OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWM2ZDBcdWM4MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmNVx1YzEyMFx1YzgxMCAoQ29sbGluZWFyIFBvaW50cylcdWM3NDAgXHVkNTVjIFx1YzljMVx1YzEyMCBcdWMwYzFcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTVjXHVhYzhjIFx1YWNmNVx1YzZkMFx1YzgxMChDb2NpcmN1bGFyIFBvaW50cylcdWM3NDQgXHVkNTVjIFx1YzZkMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWJkODBcdWJkODQgXHVjOWQxXHVkNTY5IFx1YzkxMSBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjZjVcdWM2ZDBcdWM4MTBcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBYXHVjNjQwIFlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwPHN1cD40PFwvc3VwPiAmbGU7IFgsWSAmbGU7IDEwPHN1cD40PFwvc3VwPikgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjkgXHVjOTExIFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWNmNVx1YzZkMFx1YzgxMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU2OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb2NpcmN1bGFyIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IHByb2JhYmx5IGtub3cgd2hhdCBhIHNldCBvZiBjb2xsaW5lYXIgcG9pbnRzIGlzOiBhIHNldCBvZiBwb2ludHMgc3VjaCB0aGF0IHRoZXJlIGV4aXN0cyBhIHN0cmFpZ2h0IGxpbmUgdGhhdCBwYXNzZXMgdGhyb3VnaCBhbGwgb2YgdGhlbS4gQSBzZXQgb2YgY29jaXJjdWxhciBwb2ludHMgaXMgZGVcdWZiMDFuZWQgaW4gdGhlIHNhbWUgZmFzaGlvbiwgYnV0IGluc3RlYWQgb2YgYSBzdHJhaWdodCBsaW5lLCB3ZSBhc2sgdGhhdCB0aGVyZSBpcyBhIGNpcmNsZSBzdWNoIHRoYXQgZXZlcnkgcG9pbnQgb2YgdGhlIHNldCBsaWVzIG92ZXIgaXRzIHBlcmltZXRlci48XC9wPlxyXG5cclxuPHA+VGhlIEludGVybmF0aW9uYWwgQ29sbGluZWFyIFBvaW50cyBDZW50cmUgKElDUEMpIGhhcyBhc3NpZ25lZCB5b3UgdGhlIGZvbGxvd2luZyB0YXNrOiBnaXZlbiBhIHNldCBvZiBwb2ludHMsIGNhbGN1bGF0ZSB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VyIHN1YnNldCBvZiBjb2NpcmN1bGFyIHBvaW50cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIGlzIGdpdmVuIHVzaW5nIHNldmVyYWwgbGluZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluIHRoZSBzZXQgKDEgJmxlOyBOICZsZTsgMTAwKS4gRWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBYIGFuZCBZIHJlcHJlc2VudGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgYSBwb2ludCBvZiB0aGUgc2V0ICgmbWludXM7MTA8c3VwPjQ8XC9zdXA+ICZsZTsgWCwgWSAmbGU7IDEwPHN1cD40PFwvc3VwPikuIFdpdGhpbiBlYWNoIHRlc3QgY2FzZSwgbm8gdHdvIHBvaW50cyBoYXZlIHRoZSBzYW1lIGxvY2F0aW9uLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCB0ZXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25lIHplcm8uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBhIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBwb2ludHMgaW4gb25lIG9mIHRoZSBsYXJnZXN0IHN1YnNldHMgb2YgdGhlIGlucHV0IHRoYXQgYXJlIGNvY2lyY3VsYXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Latin America > Latin America Regional Contests 2010 C번