3260354_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000;
struct node1{
	int x1,y1,x2,y2;
};
struct node{
	int x,y;
};
int n,num,set[2*MAXN],cnt[2*MAXN];
node1 seg[MAXN];
node point[MAXN*2];
char str[300],a[300],b[300],c[300],d[300];
void init(){
	int i,j,k,p,q;
	for (i=0;i<n;i++){
		scanf("%d%d%d%d",&j,&k,&p,&q);
		seg[i].x1=j,seg[i].y1=k;
		seg[i].x2=p,seg[i].y2=q;
		point[2*i].x=j,point[2*i].y=k;
		point[2*i+1].x=p,point[2*i+1].y=q;
	}
}
bool cmp(node a,node b){
	if (a.x!=b.x)
		return a.x<b.x;
	else
		return a.y<b.y;
}
void sortpoint(){
	sort(point,point+2*n,cmp);
	int i,j;
	for (i=1,j=1;i<2*n;i++)
		if ((point[i].x!=point[i-1].x)||(point[i].y!=point[i-1].y)){
			point[j].x=point[i].x,point[j].y=point[i].y;
			j++;
		}
	num=j;
}
int judgeside(int x,int y,int key){
	if ((x>point[key].x)||((x==point[key].x)&&(y>point[key].y)))
		return 1;
	else if ((x==point[key].x)&&(y==point[key].y))
		return 0;
	else
		return -1;
}
int bsearch(int x,int y,int left,int right){
	if (left<=right){
		int mid=(left+right)/2;
		int key=judgeside(x,y,mid);
		if (key==0)
			return mid;
		else if (key==1)
			return bsearch(x,y,mid+1,right);
		else 
			return bsearch(x,y,left,mid-1);
	}
}
int findset(int k){
	if (set[k]==-1)
		return k;
	else
		return set[k]=findset(set[k]);
}
void solve(){
	sortpoint();
	int i,j,k,p,q;
	for (i=0;i<num;i++)
		set[i]=-1;
	memset(cnt,0,sizeof(cnt));
	for (i=0;i<n;i++){
		j=bsearch(seg[i].x1,seg[i].y1,0,num-1);
		k=bsearch(seg[i].x2,seg[i].y2,0,num-1);
		cnt[j]++,cnt[k]++;
		p=findset(j),q=findset(k);
		if (p!=q)
			set[p]=q;
	}
	for (i=0;i<num;i++)
		if ((findset(i)!=findset(0))||(cnt[i]%2==1)){
			printf("0\n");
			return;
		}
	printf("1\n");
}
int main(){
	while (scanf("%d",&n)!=EOF){
		init();
		solve();
	}
	return 0;
}