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