题目链接：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; }