MCOCIR - Cocircular Points

no tags 

 

 

English Vietnamese

 

Albert, Charles and Mary invented a new version of the classical game Bingo. In traditional
Bingo the game is presided over by a non-player known as the caller. At the beginning of the
game each player is given a card containing a unique combination of numbers from 0 to N
arranged in columns and rows. The caller has a bag containing N + 1 balls, numbered from 0
to N. On each turn, the caller randomly selects a ball from the bag, announces the number of
the drawn ball to the players, and sets the ball aside so that it cannot be selected again. Each
player searches his card for the called number and marks it if he finds it. The first player who
marks a complete pre-announced pattern on the card (for example, a full horizontal line) wins
a prize.
In the Albert-Charles-Mary version, on each turn, the caller draws a first ball, returns it to
the bag, draws a second ball, returns it to the bag, and then calls out the absolute difference
between the two ball numbers. To generate even more excitement, before the game started a
possibly empty subset of balls is removed from the bag, in such a way that at least two balls
remain there. They would like to know if every number from 0 to N may still be called out
with the new drawing method considering the balls that were left in the bag.
Input
Each test case is given using exactly two lines. The first line contains two integers N and B.
The meaning of N was described above (1 ≤ N ≤ 90), while B represents the number of balls
which remained in the bag (2 ≤ B ≤ N + 1). The second line contains B distinct integers bi,
indicating the balls which remained in the bag (0 ≤ bi ≤ N).
The last test case is followed by a line containing two zeros.
Output
For each test case output a single line containing a single uppercase ‘Y’ if is possible to call out
every number from 0 to N, inclusive, or a single uppercase ‘N’ otherwise.

 

You probably know what a set of collinear points is: a set of points such that there exists a straight line that passes through all of them. A set of cocircular points is defined in the same fashion, but instead of a straight line, we ask that there is a circle such that every point of the set lies over its perimeter.

The International Collinear Points Centre (ICPC) has assigned you the following task: given a set of points, calculate the size of the larger subset of cocircular points.

 

Input

 

Each test case is given using several lines. The first line contains an integer N representing the number of points in the set (1 ≤ N ≤ 100). Each of the next N lines contains two integers X and Y representing the coordinates of a point of the set (−10^4 ≤ X, Y ≤ 10^4 ). Within each test case, no two points have the same location. 

The last test case is followed by a line containing one zero.

 

Output

 

For each test case output a single line with a single integer representing the number of points in one of the largest subsets of the input that are cocircular.

 

Sample input

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

 

 

Output for the sample input

 5

3

2

 

 

 

 


hide comments
[Rampage] Blue.Mary: 2010-12-21 02:33:45

My solution has time complexity O(n^3logn).

David Gómez: 2010-12-20 21:49:10

Can O(N^4) get AC?

Mahesh Chandra Sharma: 2010-12-15 21:43:36

What is the time limit for C++?

Shaka Shadows: 2010-11-08 19:32:58

Problem corrected fellows. :)

.:: Pratik ::.: 2010-11-08 19:26:35

Fortune cookie is correct, can this be corrected?
Thanks

fortune cookie: 2010-11-08 19:26:35

It seems that the judge input terminates with n=0 or EOF (no zero).


Added by:~!(*(@*!@^&
Date:2010-11-04
Time limit:1s-1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC2010 – Latin American Regional