当前位置: 代码迷 >> 综合 >> poj 2606 Rabbit hunt【同一条直线上的点】
  详细解决方案

poj 2606 Rabbit hunt【同一条直线上的点】

热度:39   发布时间:2024-01-11 17:04:45.0

我想这道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;
}


  相关解决方案