83
poj 2606 Rabbit hunt【同一條直線上的點】
我想這道2606在一條線上麵殺死兔子和上一題1118的在一條線上麵投放炸彈貌似沒有什麼不同。。。如果硬要扯點不同就是1118沒有交代坐標點 的正負，而2606交代了。。。反正這種解法對於是否包含負數沒有影響
直接在上一題的基礎上改了一下就順利AC。。。
而且我這次好奇的試了一下1118中效率較低的代碼，也AC了，可能是因為這裏的N是小於200，而且隻有一組測試數據的緣故吧
AC的代碼之一（高效版）：
#include <stdio.h>
int x[202],y[202];
int main()
{
int n;
scanf("%d",&n);
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;
}
AC代碼之二（低效版）：
#include <stdio.h>
int x[202],y[202];
int main()
{
int n;
scanf("%d",&n);
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=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;
}
最後更新：2017-04-03 14:53:45