本文主要是介绍poj 2780 Linearity 【高效版 同一条直线上的点】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题才真的没有那么的水，可能因为测试数据很多，然后又每个数据有1000个点要处理，用O（n^3）的三重循环直接TLE掉了。。。
所以得另想办法，后来参考了一下别人的想法，得用极角排序，一个sort（）就可以了，极角为0的因为无法做分母，所以得单独考虑，终于AC。。。
AC的代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>using namespace std;int x[1002],y[1002];int main()
{int n;int i,j,k,max;while(scanf("%d",&n)!=EOF){//输入for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);max=2;//每次循环都判断for(k=1;k<=n;k++){int count1=1;double angle[1002];int zero=0;for(i=1;i<=n;i++){//单独处理分母为0的情况if(x[i]-x[k]==0)zero++;elseangle[count1++]=(double)(y[i]-y[k])/(double)(x[i]-x[k]);}//按极角的大小进行排序sort(&angle[1],&angle[count1]);//看排序的里面有几个连续的数int temp=2;int sum=2;double pos=angle[1];for(i=2;i<count1;i++){//是相同的就count++if(pos==angle[i])sum++;//否则就重头开始计数else{pos=angle[i];if(sum>temp) temp=sum; sum=2;}}if(temp>max) max=temp;if(zero>max) max=zero;}printf("%d\n",max);}return 0;
}
TLE的代码：
#include <stdio.h>int x[1002],y[1002];int main()
{int n;while(scanf("%d",&n)!=EOF){int i;//输入坐标点的值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 2780 Linearity 【高效版 同一条直线上的点】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
