Posted on 2010-07-31 21:09
Kevin_Zhang 阅读(216)
评论(0) 编辑 收藏 引用 所属分类:
计算几何
这道题没有AC，提交的人也比较少，只有一个人AC，不知道是怎么AC的，题意我理解为求不相同的点的个，代码是正确的，但是提交却是WA，不知道原因。
写这个程序时，犯了一个常识性错误。想写n+=2；却写成n=+2;结果一开始就进入死循环，运行后没反应，还调了好一会才发现错误，写程序需要认真。
/*zoj1615分析求不同点的个数，实现方法
1）取一个点和剩下尚未比较过的点比较，如果为相同点，将这个相同的点去掉，更新结果，直到比较完为止，时间复杂度为O（n^2）;
2）先对所有点进行排序，排序规则是X有先，y次之的升序排列，然后从前往后检测，如x,y均相等，则结果减1，这种方法主要是排序上。O（nlogn+n）;
*/
//下面根据方法一写代码
//Source code
#include"iostream"
#include"stdio.h"
using namespace std;
int result;
struct point{
int x;
int y;
int flag;
}p[16];
int main()
{
int t,n;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
scanf("%d",&n);
result=2*n;
for(int k=0;k<2*n;k=k+2)
{
scanf("%d%d%d%d",&p[k].x ,&p[k].y ,&p[k+1].x ,&p[k+1].y );
p[k].flag =0;
p[k+1].flag =0;
}
/* for(int k=0;k<2*n;k=k+2)
{
cout<<p[k].x <<" "<<p[k].y <<" "<<p[k].flag <<" "<<p[k+1].x <<" "<<p[k+1].y<<" " <<p[k+1].flag <<endl;
}*/
for(int j=0;j<2*n-1;j++)
{ if(p[j].flag)continue;
for(int k=j+1;k<2*n;k++)
{if(!p[k].flag&&p[j].x ==p[k].x &&p[j].y ==p[k].y )
{p[k].flag =1;result--;}
else continue;
}
}
printf("%d\n",result);
}
return 0;
}