326
poj 1118 Lining Up【同一条直线上的点】
这道题总算没有让我感觉超级水，至少我还超时了一次。。。哈哈哈
题意还比较容易懂：给出 n 个点的整数坐标（n<=700），求一条直线，使得在这条直线上的点数最多，输出点数。
解题思路：采用几何中的三个点是否在一条直线上判定定理：(yi-yk)/(xi-xk)=(yj-yk)/(xj-xk)，除法不能出现分母为0的情况，所以转换为乘法做（而且乘法效率也高些），即：(y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])（i、j、k共线）。
暴搜肯定尽量追求不重不漏，重了会超时（因为三重循环重复count，我就超了一次），漏了必然WA。。。
另外我发现OJ上可以在循环里面定义变量
超时的代码：
#include <stdio.h>
int x[702],y[702];
int main()
{
int n;
int i;
while(scanf("%d",&n))
{
if(n==0)
return 0;
//输入坐标点的值
for(i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
//暴搜开始
int count,max=-1;
int j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(j==i)
continue;
count=2;
for(k=1;k<=n;k++)
{
if(k==i || k==j)
continue;
if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k]))
count++;
}
if(max<count) max=count;
}
printf("%d\n",max);
}
return 0;
}
后来改进，AC的代码：
#include <stdio.h>
int x[702],y[702];
int main()
{
int n;
int i;
while(scanf("%d",&n))
{
if(n==0)
return 0;
//输入坐标点的值
for(i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
//暴搜开始
int count,max=-1;
int j,k;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
count=2;
for(k=j+1;k<=n;k++)
if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])) count++;
if(max<count) max=count;
}
printf("%d\n",max);
}
return 0;
}
最后更新：2017-04-03 14:53:45