Sgu/128

by hza

#include<stdio.h>
#include<stdlib.h> 
 
const int MAX=10000;
const int maxn=15000,maxm=50000;
int l[maxm],r[maxm],mid[maxm],lc[maxm],rc[maxm],count[maxm];
int x[maxn],y[maxn],z[maxn],deg[maxn],fa[maxn];
int ans,total,n,root;
bool fl[maxn];
 
void seg_build(int ll,int rr,int&t)
{
   t=++total;
   l[t]=ll;r[t]=rr;mid[t]=(ll+rr)>>1;
   if (ll==rr) return;
   seg_build(ll,mid[t],lc[t]);
   seg_build(mid[t]+1,rr,rc[t]);
}
 
void seg_insert(int pt)
{
   for (int t=1;;)
   {
      ++count[t];
      if (l[t]==r[t]) break;
      if (pt<=mid[t]) t=lc[t];else t=rc[t];
   }
}
 
void seg_remove(int pt)
{
   for (int t=1;;)
   {
      --count[t];
      if (l[t]==r[t]) break;
      if (pt<=mid[t]) t=lc[t];else t=rc[t];
   }
}
 
bool seg_cross(int ll,int rr,int t)
{
   if (ll==l[t]&&rr==r[t]) return count[t]!=0;
   else if (rr<=mid[t]) return seg_cross(ll,rr,lc[t]); 
   else if (ll> mid[t]) return seg_cross(ll,rr,rc[t]);
   else return seg_cross(ll,mid[t],lc[t])||seg_cross(mid[t]+1,rr,rc[t]);
}
 
bool check_cross()
{
   seg_build(-10000,10000,root);
   int i=0,s;
   for (;;)
   {
      s=++i;
      if (s>n) break;
      while (y[i]==y[i+1]) i++;
      for (int j=s;j<=i;++j) if (fl[j]) seg_insert(x[j]);
      for (int j=s;j<i;j+=2) if (x[j+1]-x[j]>1&&seg_cross(x[j]+1,x[j+1]-1,1)) return false;
      for (int j=s;j<=i;++j) if (!fl[j]) seg_remove(x[j]);
   }
   return true;
}
 
void sort_x(int l,int r)
{
   	int i=l,j=r,mid=x[(l+r)>>1],mid2=y[(l+r)>>1],tmp;
   	while (i<=j)
   	{
      	while (x[i]<mid||(x[i]==mid&&y[i]<mid2)) i++;
      	while (x[j]>mid||(x[j]==mid&&y[j]>mid2)) j--;
		if (i<=j)
      	{
			tmp=x[i];x[i]=x[j];x[j]=tmp;
         	tmp=y[i];y[i]=y[j];y[j]=tmp;
         	tmp=z[i];z[i]=z[j];z[j]=tmp;
         	i++;j--;
      	}
   	}
   	if (i<r) sort_x(i,r);
   	if (l<j) sort_x(l,j);
}
 
void sort_y(int l,int r)
{
   int i=l,j=r,mid=y[(l+r)>>1],mid2=x[(l+r)>>1],tmp;
   bool tb;
   while (i<=j)
   {
      while (y[i]<mid||(y[i]==mid&&x[i]<mid2)) i++;
      while (y[j]>mid||(y[j]==mid&&x[j]>mid2)) j--;
      if (i<=j)
      {
         tmp=x[i];x[i]=x[j];x[j]=tmp;
         tmp=y[i];y[i]=y[j];y[j]=tmp;
         tmp=z[i];z[i]=z[j];z[j]=tmp;
         tb=fl[i];fl[i]=fl[j];fl[j]=tb;
         i++;j--;
      }
   }
   if (i<r) sort_y(i,r);
   if (l<j) sort_y(l,j);
}
 
int find_father(int i)
{
	if(i!=fa[i])
		return fa[i]=find_father(fa[i]);
	return i;
}
 
bool check_set()
{
	int t=find_father(1);
	for(int i=1;i<=n;++i)
		if(find_father(i)!=t||deg[i]!=2)return false;
	return true;
}
 
bool connect()
{
	sort_x(1,n);
	for(int i=1;i<n;i+=2)
	{
		if(x[i]!=x[i+1])return false;
		ans+=y[i+1]-y[i];
		++deg[z[i]];++deg[z[i+1]];
		fl[i]=true;fl[i+1]=false;
      	int a=find_father(z[i]);
      	int b=find_father(z[i+1]);
	  	fa[a]=b;
	}
	sort_y(1,n);
	for(int i=1;i<n;i+=2)
	{
		if(y[i]!=y[i+1])return false;;
		ans+=x[i+1]-x[i];
		++deg[z[i]];++deg[z[i+1]];
      	int a=find_father(z[i]);
      	int b=find_father(z[i+1]);
	  	fa[a]=b;
	}
	return true;
}
 
bool read()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i],z[i]=i);
	for(int i=1;i<=MAX;++i)fa[i]=i;
	if(n%2==1)return false;
	ans=0;
	return true;
}
 
bool work()
{
	if(!connect())return false;
	if(!check_set())return false;
	if(!check_cross())return false;
	return true;
}
 
int main()
{
	freopen("snack.in","r",stdin);freopen("snack.out","w",stdout);
	read();
	if(!work())ans=0;
	printf("%d\n",ans);
}

/by Logic
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=15050,maxr=20050,add=10001;
struct Point
{
	int id,x,y,d;
}p[maxn];
int n,ans=0,con[maxn][2],tree[maxr]={0};
bool cmp1(const Point &xx,const Point &yy) {return xx.x<yy.x||(xx.x==yy.x&&xx.y<yy.y);}
bool cmp2(const Point &xx,const Point &yy) {return xx.y<yy.y||(xx.y==yy.y&&xx.x<yy.x);}
bool cmp3(const Point &xx,const Point &yy) {return xx.y<yy.y||(xx.y==yy.y&&xx.d>yy.d);}
inline int lowbit(int x) {return x&(-x);}
void ins(int x)
{
	while(x<maxr)
		tree[x]++,x+=lowbit(x);
}
void del(int x)
{
	while(x<maxr)
		tree[x]--,x+=lowbit(x);
}
int que(int x)
{
	int s=0;
	while(x)
		s+=tree[x],x-=lowbit(x);
	return s;
}
int work()
{
	int i,j,n0=n,s=0;
	if(n&1) return 0;
	sort(p,p+n0,cmp1);
	for(i=0;i<n0;i=j)
		for(j=i;j<n0&&p[j].x==p[i].x;j+=2)
			if(p[j+1].x!=p[j].x)
				return 0;
			else
			{
				p[j].d=-1,p[j+1].d=1;
				con[p[j].id][0]=p[j+1].id;
				con[p[j+1].id][0]=p[j].id;
				ans+=p[j+1].y-p[j].y;
			}
	sort(p,p+n0,cmp2);
	for(i=0;i<n0;i=j)
		for(j=i;j<n0&&p[j].y==p[i].y;j+=2)
			if(p[j+1].y!=p[j].y) 
				return 0;
			else 
			{
				p[n].x=p[j].x*maxr+p[j+1].x,p[n].y=p[j].y;
				p[n++].d=0;
				con[p[j].id][1]=p[j+1].id;
				con[p[j+1].id][1]=p[j].id;
				ans+=p[j+1].x-p[j].x;
			}
	i=0,j=-1;
	do
	{
		if(con[i][0]!=j) j=i,i=con[i][0];
		else j=i,i=con[i][1];
		s++;
	}while(i);
	if(s<n0) return 0;
	sort(p,p+n,cmp3);
	for(i=0;i<n;i++)
		if(p[i].d<0)
			ins(p[i].x);
		else if(p[i].d>0)
			del(p[i].x);
		else if(que(p[i].x%maxr)-que(p[i].x/maxr)) 
			return 0;
	return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		p[i].id=i,scanf("%d%d",&p[i].x,&p[i].y),p[i].x+=add,p[i].y+=add;
	printf("%d\n",work());
	return 0;
}