POJ2606 Rabbit hunt【水题】

Rabbit hunt Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 8199 Accepted: 4094

Description

A good hunter kills two rabbits with one shot. Of course, it can be easily done since for any two points we can always draw a line containing the both. But killing three or more rabbits in one shot is much more difficult task. To be the best hunter in the world one should be able to kill the maximal possible number of rabbits. Assume that rabbit is a point on the plane with integer x and y coordinates. Having a set of rabbits you are to find the largest number K of rabbits that can be killed with single shot, i.e. maximum number of points lying exactly on the same line. No two rabbits sit at one point.

Input

An input contains an integer N (2<=N<=200) specifying the number of rabbits. Each of the next N lines in the input contains the x coordinate and the y coordinate (in this order) separated by a space (-1000<=x,y<=1000).

Output

The output contains the maximal number K of rabbits situated in one line.

Sample Input

6 7 122 8 139 9 156 10 173 11 190 -100 1

Sample Output

5

Source

Ural State University collegiate programming contest 2000

问题链接：POJ2606 Rabbit hunt。

题意简述：输入n，输入n个整数对，即n个坐标点，问最多共线点数是多少。

问题分析：用暴力法解决这个问题，好在计算规模不算大。

程序说明：

  判断共线时，使用的是乘法，没有用除法，可以保证精确的计算结果。

  这个问题与POJ1118 HDU1432 Lining Up基本上相同，只是输入数据格式略有不同。

AC的C语言程序如下：

/* POJ2606 Rabbit hunt */ #include <stdio.h> #define MAXN 200 struct { int x, y; } p[MAXN+1]; /* point */ int main(void) { int n, ans, max, i, j, k; scanf("%d", &n); for(i=0; i<n; i++) scanf("%d%d", &p[i].x, &p[i].y); ans = 2; for(i=0; i<n; i++) for(j=i+1; j<n; j++) { max = 2; for(k=j+1; k<n; k++) if ((p[j].x - p[i].x)*(p[k].y - p[j].y) == (p[j].y - p[i].y)*(p[k].x - p[j].x)) max++; if(max > ans) ans = max; } printf("%d\n", ans); return 0; }