Sgu 128 Snake

タイトル接続:http://acm.sgu.ru/problem.php?contest=0&problem=128
題意:n個の点を与える.このn個の点に線を結んで、満足させます:
1.このn個の点線を結んだ後に形成される折れ線は閉じている.
2.折れ線には、すべてのn個の点が含まれ、このn個の点のみが含まれている必要があります.
3.折れ線の中で隣接する線分は90度の角度を形成しなければならない.
4.各線分は座標軸に平行でなければならない.すなわち、x方向とy方向の線分しかない.
5.形成された線分は自己交差できない.
6.折れ線は最小の長さでなければなりません.
分析:前の4つの条件に合致する折れ線の答えは1つしかないことを証明することができます.各点から2つの線分しか発散できず、1つは縦線、1つは横線であることが証明されているからです.
また、x軸に平行な線分を例として、(x 1,y)、(x 2,y)、(x 3,y)、(x 4,y)、(x 5,y)、(x 6,y).まず点数は偶数でなければならないが、次に、連法はx 1-x 2,x 3-x 4,x 5-x 5である.
y軸に平行な線分もそうです.
次に,形成された唯一の図形が自己交差しているかどうかを判断すればよい.
線分ツリーを利用して判断することができます.
私たちはこうします.
x周に平行な線分(x 1,x 2)を順次走査する.(x 1,x 2−1)の区間に点マークが存在する場合、肯定マークの点は縦線を形成し、貫通(x 1,x 2−1)、すなわち交差が存在する.
x 1ポイントがアクセスされていない場合、update(1)は、すでにアクセスされている場合、update(-1)は、閉じた相互相殺に相当し、以降の判断に影響を及ぼさない.x 2点は類似している.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

#define Maxn 20100
#define lx (x<<1)
#define rx ((x<<1) | 1)
#define MID ((l + r)>>1)

struct Point
{
	int x,y;
}p[Maxn];

vector <int> s[Maxn<<2],match[Maxn];
int maxx,ans,vis[Maxn],S[Maxn<<2];

bool cmpy(int a,int b) {return p[a].y<p[b].y;}
bool cmpx(int a,int b) {return p[a].x<p[b].x;}

void init()
{
	maxx = 0;
	ans = 0	;
	memset(vis,0,sizeof(vis));
	memset(S,0,sizeof(S));
	memset(match,0,sizeof(match));
}
void dfs(int i)
{
	vis[i] = 1;
	for(int k=0;k<2;k++)
	{
		if(!vis[match[i][k]]) dfs(match[i][k]);
	}
}
void pushUp(int x)
{
	S[x] = S[lx] + S[rx];
}
void update(int p,int d,int l,int r,int x)
{
	if(l==r)
	{
		S[x] += d;
		return;
	}
	if(p<=MID) update(p,d,l,MID,lx);
    else update(p,d,MID+1,r,rx);
    pushUp(x);
}
int query(int L,int R,int l,int r,int x)
{
	if(L<=l && r<=R)
	{
		return S[x];
	}
	int ans = 0;
	if(L<=MID) ans += query(L,R,l,MID,lx);
	if(MID<R) ans += query(L,R,MID+1,r,rx);
	return ans;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int n;
	scanf(" %d",&n);
	init();
	for(int i=1;i<=n;i++)
	{
		scanf(" %d %d",&p[i].x,&p[i].y);
		p[i].x += 10001,p[i].y += 10001;
		maxx = max(maxx,max(p[i].x,p[i].y));
	}
	//x
	for(int i=1;i<=n;i++) s[p[i].x].push_back(i);

	for(int i=1;i<=maxx;i++)
	{
		if(s[i].size())
		{
			if(s[i].size()&1) goto L1;
			sort(s[i].begin(),s[i].end(),cmpy);
			for(int j=0;j<s[i].size();j+=2)
			{
				ans += p[s[i][j+1]].y - p[s[i][j]].y;
				match[s[i][j+1]].push_back(s[i][j]);
				match[s[i][j]].push_back(s[i][j+1]);
			}
			s[i].clear();
		}
	}

	//y
	for(int i=1;i<=n;i++) s[p[i].y].push_back(i);

	for(int i=1;i<=maxx;i++)
	{
		if(s[i].size())
		{
			if(s[i].size()&1) goto L1;
			sort(s[i].begin(),s[i].end(),cmpx);
			for(int j=0;j<s[i].size();j+=2)
			{
				ans += p[s[i][j+1]].x - p[s[i][j]].x;
				match[s[i][j+1]].push_back(s[i][j]);
				match[s[i][j]].push_back(s[i][j+1]);
			}
			//s[i].clear();
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(match[i].size()!=2) goto L1;
	}
	//  
	dfs(1);
	for(int i=1;i<=n;i++) if(!vis[i]) goto L1;
	memset(vis,0,sizeof(vis));
	//    
	for(int i=1;i<=maxx;i++)
	{
		if(s[i].size())
		{
			for(int j=0;j<s[i].size();j+=2)
			{
				int x1 = p[s[i][j]].x;
				int x2 = p[s[i][j+1]].x;
				if(x2-x1>1 && (query(1,x2-1,1,maxx,1) - query(1,x1,1,maxx,1))>0)
					goto L1;
				if(!vis[x1]) update(x1,1,1,maxx,1);
				else update(x1,-1,1,maxx,1);
				if(!vis[x2]) update(x2,1,1,maxx,1);
				else update(x2,-1,1,maxx,1);
				vis[x1] = !vis[x1];
				vis[x2] = !vis[x2];
			}
		}
	}
	printf("%d
",ans);
	return 0;
	L1: puts("0");
    return 0;
}