DWITE Online Computer Programming Contest
February 2006

Problem 1

Points on a Line

In this particular problem, you will be given a set of points that lie on the Cartesian plane. Given two points, p₁ and p₂, determine how many points in the set lie on the line created by p₁ and p₂.

The input will contain one set of data. The first line will contain N, the number of points in the set, 10 ≤ N ≤ 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. -1000 ≤ x, y ≤ 1000. After these N lines, there will be five lines that will contain the coordinates of the points p₁ and p₂; p₁ and p₂ are not part of the original set. -1000 ≤ p₁ and p₂ ≤ 1000.

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₁ and p₂.

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).

All Submissions
Best Solutions

Point Value: 7
Time Limit: 1.00s
Memory Limit: 16M
Added: Nov 13, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)