uva 11106

題目鏈接：uva 11106 - Rectilinear Polygon

題目大意：給出若干個點，判斷說能否將這若干個點連成一個全為直角的圖形，要求沒有一條線段經過三點。輸出圖形的周長。

解題思路：首先同以橫坐標相鄰的兩個一定相連，同理縱坐標。然後會由說可能選完的的邊出現了相交的情況或者說不止一個圖形。

不止一個圖形比較好解決，並查集判斷所有點是否聯通。

相交的情況就比較復雜，在處理橫坐標的時候，將所有邊保存y1，y2，和x，然後按照y1較小的排序。

在處理縱坐標的邊時，每選取兩點進行判斷選擇，y1 < y，進入優先隊列，隊列中按照y2大小排序。

然後y2 < y的則要出隊。

但是因為後面要判斷有沒有交點，需遍歷優先隊列，所以我就用鏈表優化，減少刪除時移動元素的開銷。

#include 
#include 
#include 
#include 

using namespace std;
const int N = 100005;

struct point {
	int x, y, t, id;
	friend bool operator < (const point& a, const point& b) {
		return a.y > b.y;
	}
}p[N], s[N];

struct node {
	int t;
	node* link;
	node(int t) { 
		this->t = t;
		this->link = NULL; 
	}
};

int n, m, f[N];

int getfar(int x) {
	return x == f[x] ? x : f[x] = getfar(f[x]);
}

bool cmpX(const point& a, const point& b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool cmpY(const point& a, const point& b) {
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

void init() {
	m = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &p[i].x, &p[i].y);
		f[i] = p[i].id = i;
	}
	sort(p, p + n, cmpX);
}

void del(node* first, int x) {
	node* far = first;
	node* mov = first->link;
	while (mov != NULL) {
		if (mov->t == x) {
			far->link = mov->link;
			delete mov;
			return;
		}
		far = mov;
		mov = mov->link;
	}
}

int solve() {
	if (n&1) return -1;
	bool flag = false;
	int ans = 0;

	for (int i = 0; i < n; i += 2) {
		if (p[i].x != p[i+1].x) return -1;
		ans += p[i+1].y - p[i].y;
		s[m].x = p[i].y, s[m].y = p[i+1].y, s[m].t = p[i].x, m++;
		f[getfar(p[i].id)] = getfar(p[i+1].id);
	}
	int tmp = m, v = 0;
	sort(s, s + m, cmpX);
	sort(p, p + n, cmpY);
	priority_queue que;
	node* first = new node(0);

	for (int i = 0; i < n; i+= 2) {
		if (p[i].y != p[i+1].y) {
			flag = true; break;
		}
	
		while (v < m) {
			if (s[v].x < p[i].y) {
				que.push(s[v]);
				node* p = new node(s[v].t);
				p->link = first->link; first->link = p;
			} else break;
			v++;
		}

		while (!que.empty()) {
			point c = que.top();
			if (c.y <= p[i].y) {
				del(first, c.t);
				que.pop();
			}
			else break;
		}

		node* mov = first->link;
		while (mov != NULL) {
			if (mov->t > p[i].x && mov->t < p[i+1].x) {
				flag = true; break;
			}
			mov = mov->link;	
		}

		if (flag) break;

		ans += p[i+1].x - p[i].x;
		if (getfar(p[i].id) != getfar(p[i+1].id)) {
			f[getfar(p[i].id)] = getfar(p[i+1].id);
			tmp--;
		}
	}
	while (first != NULL) {
		node* c = first->link;
		first = first->link;
		delete c;
	}
	return tmp > 1 || flag ? -1 : ans;
}

int main() {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}