学步园

题意：给出n个点的整数坐标(n<=700)，求一条直线，使得在这条直线上的点数最多，输出点数

思路：对每个点i,求其余每个点j到他的斜率，记录下并排序，再统计有多少斜率一样的。求出最大值。（也许解释的不很清楚，不明白的可一留言）

错误：

1. 要判断在同一条竖线上的情况

2. 忘了自己到自己的斜率不能算上

统计：192k, 313ms, 4Y

#include <iostream><br /> #include <algorithm><br /> #define F(i,a,b) for (int i=a;i<=b;i++)<br /> using namespace std;</p> <p>int x[701], y[701], n;<br /> double a[701];</p> <p>int main()<br /> {<br /> while ( scanf("%d", &n) && n !=0 )<br /> {<br /> F(i,1,n)<br /> scanf("%d%d", &x[i], &y[i]);</p> <p> int Max = 0;<br /> F(i,1,n)<br /> {<br /> int t = 0;<br /> F(j,1,n)<br /> {<br /> if (i == j)<br /> continue;<br /> if ( x[i] == x[j] )<br /> a[++t] = 9999999;<br /> else<br /> a[++t] = ((double)y[j] - y[i] )/(x[j] - x[i]) ;<br /> }<br /> sort(&a[1], &a[t+1]);<br /> int now=1;<br /> F(j,2, n)<br /> {<br /> if (a[j] == a[j-1] )<br /> now++;<br /> else<br /> {<br /> Max = Max > now ? Max : now ;<br /> now = 1;<br /> }<br /> }<br /> }<br /> printf("%d/n", Max+1);<br /> }</p> <p> return 0;<br /> }</p> <p>