326
技術社區[雲棲]
poj 1118 Lining Up【同一條直線上的點】
這道題總算沒有讓我感覺超級水，至少我還超時了一次。。。哈哈哈
題意還比較容易懂：給出 n 個點的整數坐標（n<=700），求一條直線，使得在這條直線上的點數最多，輸出點數。
解題思路：采用幾何中的三個點是否在一條直線上判定定理：(yi-yk)/(xi-xk)=(yj-yk)/(xj-xk)，除法不能出現分母為0的情況，所以轉換為乘法做（而且乘法效率也高些），即：(y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])（i、j、k共線）。
暴搜肯定盡量追求不重不漏，重了會超時（因為三重循環重複count，我就超了一次），漏了必然WA。。。
另外我發現OJ上可以在循環裏麵定義變量
超時的代碼：
#include <stdio.h>
int x[702],y[702];
int main()
{
int n;
int i;
while(scanf("%d",&n))
{
if(n==0)
return 0;
//輸入坐標點的值
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=1;j<=n;j++)
{
if(j==i)
continue;
count=2;
for(k=1;k<=n;k++)
{
if(k==i || k==j)
continue;
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;
}
後來改進，AC的代碼：
#include <stdio.h>
int x[702],y[702];
int main()
{
int n;
int i;
while(scanf("%d",&n))
{
if(n==0)
return 0;
//輸入坐標點的值
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:45