本文主要是介绍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;
}这篇关于poj 1118 Lining Up【同一条直线上的点】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
