Posted on 2010-07-31 21:09
Kevin_Zhang 閱讀(268)
評論(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;
}