A perfect point set is a set of points, for every point (x,y) in this set, point (y,x) is also in this set.
Input
There are mutical cases for this problem. For every input case, there is a set. we give you the number of points in this set in the first line, followed by n lines,each give two integers x y.
Output
If this set is a perfect set, you should print "Yes", else you print "No".
Sample Input
4
1 4
4 1
2 5
5 2
Sample Output
Yes
1,这种类似稀疏矩阵的数组对一般不用数组存储,用结构体比较好
2,排序后比较非常的巧妙。
#include<iostream>
#include<cstdlib>
using namespace std;
struct mm{
double a;
double b;}M[100000];
bool operator<(mm m1,mm m2)
{
if(m1.a<m2.a)
return true;
else
{
if(m1.a==m2.a&&m1.b<m2.b)
return true;
}
return false;
}
int main()
{
// freopen("s.txt","r",stdin);
// freopen("key.txt","w",stdout);
int num;
double a,b;
int temp=0;
while(cin>>num)
{
memset(M,0,sizeof(M));
temp=0;
for(int k=0;k<num;k++)
{
cin>>a>>b;
if(a<b)
{
M[temp].a=a;
M[temp].b=b;
temp++;
}
else if(a>b)//把a和b相等的都去掉了
{
M[temp].a=b;
M[temp].b=a;
temp++;
}
}
if(temp%2!=0)cout<<"No"<<endl;
else
{
sort(M,M+temp);
int flag=0;
for(int p=0;p<temp;p+=2)
{
if(M[p].b!=M[p+1].b||M[p].a!=M[p+1].a)
{
flag=1;break;
}
}
if(flag==0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
//system("PAUSE");
return 0;
}
posted on 2009-07-03 16:43
luis 阅读(338)
评论(0) 编辑 收藏 引用 所属分类:
格式.输入输出.数据类型