UVA 11106 - Rectilinear Polygon（几何+贪心） - c++编程基础

Problem B: Rectilinear polygon

Given is n points with integer coordinates in the plane. Is it is pZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3NpYmxlIHRvIGNvbnN0cnVjdCBhIHNpbXBsZSwgdGhhdCBpcyBub24taW50ZXJzZWN0aW5nLCByZWN0aWxpbmVhciBwb2x5Z29uIHdpdGggdGhlIGdpdmVuIHBvaW50cyBhcyB2ZXJ0aWNlcz8gSW4gYSByZWN0aWxpbmVhciBwb2x5Z29uIHRoZXJlIGFyZSBhdCBsZWFzdCA0IHZlcnRpY2VzIGFuZCBldmVyeSBlZGdlIGlzIGVpdGhlciBob3Jpem9udGFsIG9yIHZlcnRpY2FsOwogZWFjaCB2ZXJ0ZXggaXMgYW4gZW5kcG9pbnQgb2YgZXhhY3RseSBvbmUgaG9yaXpvbnRhbCBlZGdlIGFuZCBvbmUgdmVydGljYWwgZWRnZS4gVGhlcmUgYXJlIG5vIGhvbGVzIGluIGEgcG9seWdvbi4KPHA+PC9wPgo8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNhc2VzIHRoYXQgZm9sbG93LiBUaGUgaW5wdXQgb2YgZWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgNCCh3CBuodwgMTAwMDAwIGdpdmluZyB0aGUgbnVtYmVyIG9mIHBvaW50cyBmb3IgdGhpcyB0ZXN0IGNhc2UuIEl0IGlzIGZvbGxvd2VkIGJ5IG4gcGFpcnMKIG9mIGludGVnZXJzIHNwZWNpZnlpbmcgdGhlIHggYW5kIHljb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzIGZvciB0aGlzIGNhc2UuPC9wPgo8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBsaW5lIGZvciBlYWNoIGNhc2Ugb24gaW5wdXQuIEVhY2ggbGluZSBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciBudW1iZXIgZ2l2aW5nIHRoZSBsZW5ndGggb2YgdGhlIHJlY3RpbGluZWFyIHBvbHlnb24gcGFzc2luZyB0aHJvdWdodCB0aGUgZ2l2ZW4gcG9pbnRzIHdoZW4gaXQgZXhpc3RzOyBvdGhlcndpc2UsIGl0CiBzaG91bGQgY29udGFpbiA8dHQ+LTE8L3R0Pi48L3A+CjxoMz5TYW1wbGUgaW5wdXQ8L2gzPgo8cHJlIGNsYXNzPQ=="brush:java;">1 8 1 2 1 0 2 1 2 2 3 2 3 1 4 0 4 2

Output for sample input

题意：给定n个点，判断这n点能不能组成一个多边形，并且点都在直角上，如果可以输出周长，不行输出-1.

思路：对于横坐标为x的所有点，如果是奇数个点，那么肯定不行，因为同一横坐标x的点，要能折出去再折回来，必然为偶数个，按x优先，y第二优先排序后，组成的边必然为，0,1组，2,3组，3,4组...对于纵坐标也是同理，这样就能求出周长了。然后在去判断有没有自交，判断方式为，先把所有以x求出来的线段保存下来，然后在求y的时候，去判断有没有相交的边（这步用了map，不过跑起来时间还是很短）。最后还要判断组合出来的多边形是否只有一个。判断方式是，之前求线段的时候，把每个点水平和垂直连的点都求出来，随便选一点进行dfs，判断最后形成环的时候，点的个数等不等于n。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
      #include 
      
        using namespace std; const int N = 100005; typedef pair
       
         pi; map
        
          vis; int t, n, en, vi[N], num; struct Point { int x, y, id, v, h; } p[N]; struct Edge { int x, y1, y2; } e[N]; bool cmp1(Point a, Point b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } bool cmp2(Point a, Point b) { if (a.y != b.y) return a.y < b.y; return a.x < b.x; } bool cmp3(Point a, Point b) { return a.id < b.id; } void init() { en = 0; vis.clear(); memset(vi, 0, sizeof(vi)); num = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &p[i].x, &p[i].y); p[i].id = i; } } void dfs(int id, int bo) { if (vi[id]) return; vi[id] = 1; num++; if (bo) dfs(p[id].v, 0); else dfs(p[id].h, 1); } int solve() { if (n % 2) return -1; int ans = 0; sort(p, p + n, cmp1); int i, save = -1; for (i = 0; i < n; i += 2) { if (p[i].x != p[i + 1].x) return -1; if (save != p[i].x) { vis[p[i].x].first = en; if (i != 0) vis[p[i - 1].x].second = en; save = p[i].x; } e[en].x = p[i].x; e[en].y1 = p[i + 1].y; e[en++].y2 = p[i].y; p[i].h = p[i + 1].id; p[i + 1].h = p[i].id; ans += (p[i + 1].y - p[i].y); } vis[p[n - 1].x].second = en; sort(p, p + n, cmp2); for (i = 0; i < n; i += 2) { if (p[i].y != p[i + 1].y) return -1; for (int j = vis[p[i].x].second; j < vis[p[i + 1].x].first; j++) { if (e[j].y1 >= p[i].y && e[j].y2 <= p[i].y) return -1; } p[i].v = p[i + 1].id; p[i + 1].v = p[i].id; ans += (p[i + 1].x - p[i].x); } sort(p, p + n, cmp3); dfs(0, 0); if (num != n) return -1; return ans; } int main() { scanf("%d", &t); while (t--) { init(); printf("%d\n", solve()); } return 0; }