LINES - Game of Lines


Farmer John has challenged Bessie to the following game: FJ has a board with dots marked at N (2 ≤ N ≤ 200) distinct lattice points. Dot i has the integer coordinates Xi and Yi (-1,000 ≤ Xi, Yi ≤ 1,000).

Bessie can score a point in the game by picking two of the dots and drawing a straight line between them; however, she is not allowed to draw a line if she has already drawn another line parallel to it. Bessie would like to know her chances of winning, so she has asked you to help find the maximum score she can obtain.

Input

There will be multiple test cases. For each case, the first line contains the integer N, and each of the next N lines gives a pair of integers, Xi and Yi. The file ends with the case N = 0, which should not be processed.

Output

For each test case, print a single integer representing the maximum number of lines Bessie can draw, no two of which are parallel.

Example

Input:
4
-1 1
-2 0
0 0
1 1
0

Output:
4

Bessie can draw lines of the following four slopes: -1, 0, ⅓, and 1.


hide comments
hafiz031: 2018-04-21 23:09:03

I used set to store all unique tangent values and stored a large number greater than possible input values for infinite case...and it worked!!...don't worry about +ve or -ve inf as they are parallel and we can take only one either one or both of them occur...finally I printed the size of the set.

amulyagaur: 2017-05-19 09:06:28

stl rockssss

Ray Brish Bhanu: 2016-08-18 15:34:59

take care of infinity slope and - infinity slope

minhthai: 2016-02-12 10:29:20

help! can someone give a tricky test case?
edit: ok wrong input gives me 4 WAs, worth it...

Last edit: 2016-02-12 10:50:42
ASHUTOSH DWIVEDI: 2015-08-21 21:40:01

easy with STL but can be done without STL....

shantanu tripathi: 2015-08-10 14:01:16

yes @mayank pratap.... made easy through STL

[Mayank Pratap]: 2015-07-31 15:26:15

STL becoming easier day by day... :)

Dhruv Mullick: 2015-05-25 21:48:52

Slope = infinity and -infinity give the same line

krishna kumar: 2014-07-03 10:41:56

sam algo gav WA in python ..... but right in C++ ...
Dont get the point ???

krishna kumar: 2014-07-03 10:41:56

sam algo gav WA in python ..... but right in C++ ...
Dont get the point ???


Added by:Neal Wu
Date:2008-10-19
Time limit:0.421s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:USACO Feb 2008