当前位置: 代码迷 >> 综合 >> poj 2780 Linearity 【高效版 同一条直线上的点】
  详细解决方案

poj 2780 Linearity 【高效版 同一条直线上的点】

热度:9   发布时间:2024-01-11 17:04:31.0

这道题才真的没有那么的水,可能因为测试数据很多,然后又每个数据有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;
}