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++;

				else
					angle[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;
}