SGU 128 Snakes

對於每一個節點，都要連出兩條線

一條沿X軸，一條沿Y軸

所以可以知道一定是如下圖







對於X軸及Y軸方向，皆是如此

連完之後，要判斷是否全部都在同一集合中（並查集）

然後要判斷會不會發生相交的情況（BIT）

//By momo
#include<cstdio>
#include<algorithm>
#define N 10010
#define M 11000
using namespace std;

int n, pos[N], up[N], in[N];

int fa[N];
void init(){ for(int i = 0; i < n; i++) fa[i] = i; }
int  find(int x){ return fa[x] = (fa[x] == x?x:find(fa[x])); }
void unio(int a, int b){ fa[find(a)] = find(b); }

struct coord{ int x, y; }co[N], que[N];
bool comx(int a, int b){
    return co[a].x < co[b].x || co[a].x == co[b].x && co[a].y < co[b].y;
}
bool comy(int a, int b){
    return co[a].y < co[b].y || co[a].y == co[b].y && co[a].x < co[b].x;
}

struct BIT{
    int dat[3*M];
    void insert(int x, int v){
        while(x < 3*M){
            dat[x] += v;
            x += x&-x;
        }
    }
    int query(int x){
        int ret = 0;
        while(x > 0){
            ret += dat[x];
            x -= x&-x;
        } return ret;
    }
}bit;

void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &co[i].x, &co[i].y);
        pos[i] = i;
    }
}

int solve(){
    int ret = 0;
    init();
    sort(pos, pos+n, comx);
    for(int x = 0; x < n; x += 2){
        int i = pos[x], j = pos[x+1];
        if(co[i].x != co[j].x) return 0;
        up[i] = j;
        ret += co[j].y - co[i].y;
        unio(i, j);
    }
    sort(pos, pos+n, comy);
    for(int x = 0; x < n; x += 2){
        int i = pos[x], j = pos[x+1];
        if(co[i].y != co[j].y) return 0;
        in[i] = 1;
        in[j] = 0;
        ret += co[j].x - co[i].x;
        unio(i, j);
    }
    int st = find(0);
    for(int i = 1; i < n; i++) if(find(i) != st) return 0;
    sort(pos, pos+n, comx);
    for(int i = 0; i < n; i++){
        int p = pos[i];
        if(up[p]){
            int v = bit.query(co[up[p]].y+M)-bit.query(co[p].y+1+M);
            if(v) return 0;
        }
        if(in[p]) bit.insert(co[p].y+1+M, 1);
        else bit.insert(co[p].y+1+M, -1);
    }
    return ret;
}

int main(){
    input();
    printf("%d\n", solve());
}