223
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;
}
最后更新：2017-04-03 14:53:48