DWITE '06 R5 #1 - Points on a Line

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 16M

Problem type
DWITE Online Computer Programming Contest, February 2006, Problem 1

In this particular problem, you will be given a set of points that lie on the Cartesian plane. Given two points, p_{1} and p_{2}, determine how many points in the set lie on the line created by p_{1} and p_{2}.

The input will contain one set of data. The first line will contain N, the number of points in the set, 10 \le N \le 100. The next N lines will contain two integers each, x and y, which represent the x-coordinate and the y-coordinate of the point. -1\,000 \le x, y \le 1\,000. After these N lines, there will be five lines that will contain the coordinates of the points p_{1} and p_{2}; p_{1} and p_{2} are not part of the original set. -1\,000 \le p_{1} and p_{2} \le 1\,000.

The output will contain five lines of data. Each line will contain the number of points in the set that lie on the line created by p_{1} and p_{2}.

Sample Input

12
0 0
-1 3
1 3
1 7
2 9
3 -1
6 0
3 1
5 3
3 5
3 8
6 6
2 2 0 4
3 0 3 9
2 2 3 3
0 4 1 5
3 -3 4 -2

Sample Output

2
4
2
1
1

Sample Input Analysis

There are 2 points [(1,3) and (3,1)] from the set that lie on the line created by the two points (2,2) and (0,4).
There are 4 points [(3,8), (3,5), (3,1) and (3,-1)] from the set that lie on the line created by the two points (3,0) and (3,9).
There are 2 points [(6,6) and (0,0)] from the set that lie on the line created by the two points (2,2) and (3,3).
There is 1 point [(-1,3)] from the set that lie on the line created by the two points (0,4) and (1,5).
There is 1 point [(6,0)] from the set that lie on the line created by the two points (3,-3) and (4,-2).


Comments

There are no comments at the moment.