Posted on 2010-07-31 21:09
Kevin_Zhang 閱讀(268)
評論(0) 編輯 收藏 引用 所屬分類:
計(jì)算幾何
這道題沒有AC，提交的人也比較少，只有一個(gè)人AC，不知道是怎么AC的，題意我理解為求不相同的點(diǎn)的個(gè)，代碼是正確的，但是提交卻是WA，不知道原因。
寫這個(gè)程序時(shí)，犯了一個(gè)常識性錯(cuò)誤。想寫n+=2；卻寫成n=+2;結(jié)果一開始就進(jìn)入死循環(huán)，運(yùn)行后沒反應(yīng)，還調(diào)了好一會才發(fā)現(xiàn)錯(cuò)誤，寫程序需要認(rèn)真。
/*zoj1615分析求不同點(diǎn)的個(gè)數(shù)，實(shí)現(xiàn)方法
1）取一個(gè)點(diǎn)和剩下尚未比較過的點(diǎn)比較，如果為相同點(diǎn)，將這個(gè)相同的點(diǎn)去掉，更新結(jié)果，直到比較完為止，時(shí)間復(fù)雜度為O（n^2）;
2）先對所有點(diǎn)進(jìn)行排序，排序規(guī)則是X有先，y次之的升序排列，然后從前往后檢測，如x,y均相等，則結(jié)果減1，這種方法主要是排序上。O（nlogn+n）;
*/
//下面根據(jù)方法一寫代碼
//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;
}