| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1152
Draw a Circle to Curse You!
Time Limit: 15000ms
Memory Limit: 65536kb Description
Fuch has a piece of magic paper, which contains many special dots. When Fuch gets annoyed by someone, he will draw a circle on that paper to curse that guy.
To make the curse come true, the circle must pass through at least three dots. We denote a circle is compatible with age k, if there are excatly k dots inside the circle. If that poor guy is k years old, the curse will come true eventually. Dots passed through by the circle are considered to be "inside", so no kid under three will be cursed. ^_^ Obviously, this paper might be unable to curse someone, if no circle compatible with his age exists. In that case, Fuch will try another way to curse that guy. To make it more easy for Fuch to curse, could you give him a list of all the possible ages? Input
The input contains multiple test cases.For each test case, the first contains two integers n (3<=n<=150), indicating the number of dots. The next n lines each contains two integers xi and yi, indicating the position of ith dot. It is guaranteed no two dots overlap each other. Test case with n=0 indicates the end of input. Don't process that test case. Output
For each test case, output the list of possible ages in ascending order in a single line. Separate each number by a single space. Output a blank line if no age is possible.
Sample Input
3 100 200 300 400 0 0 9 -2 0 -1 0 0 0 1 0 2 0 -1 1 -1 -1 1 1 1 -1 0 Sample Output
3 3 4 5 7 8 9 Source
fuch@USTC
|