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