Rectilinear polygon

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2125		Accepted: 249

Description

Given is n points with integer coordinates in the plane. Is it is possible to construct a simple, that is non-intersecting, rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least 4 vertices and every edge is either horizontal or vertical; each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon.

Input

The first line of input is an integer giving the number of cases that follow. The input of each case starts with an integer 4 ≤ n ≤ 100000 giving the number of points for this test case. It is followed by n pairs of integers specifying the x and y coordinates of the points for this case.

Output

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the rectilinear polygon passing throught the given points when it exists; otherwise, it should contain -1.

Sample Input

181 21 02 12 23 23 14 04 2

Sample Output

12 题意：平面图上给出一些点的坐标，通过这些点希望构成一类多边形，多边形中间没有洞，并且每个点是且仅是该多边形的一条横边和一条竖边的端点，且横边竖边不相交(横竖边共用一个端点的情况除外)，若给出的那些点能构成符合要求的多边形， 那么计算多边形的周长，否则输出-1. 思路：平面扫描，按照x轴扫描可以获得所有竖边的长度和，按y轴的同理，先讨论x轴的情况，将点按照x坐标大小排序后，同一列上的点按照y坐标从小到大排序，之后再观察多边形每一列的特性，可以发现每一列上点必定偶数个，相邻两个配对可以成为一条边，若出现奇数条边，肯定是构不成多边形的。按y轴扫描 也是相同做法。其次还要判断是否有横竖边相交的情况以及是否有洞(图是否连通)即可。 AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int N_MAX = 100000 + 5;#define INF 0x3f3f3f3f#define EPS 1e-10#define equals(a,b) (fabs(a-b)
                
                 S_x;Segment S_x[N_MAX];typedef Segment line;class Circle {public: point c; double r; Circle(point c = point(), double r = 0.0) :c(c), r(r) {}};typedef vector
                 
                  Polygon;//p在线段s上的投影point project(Segment s, point p) { Vector base = s.p2 - s.p1; double r = base.dot(p - s.p1) / base.norm(); return s.p1 + base*r;}//点p关于直线s的对称点point reflect(Segment s, point p) { return p + (project(s, p) - p)*2.0;}//点与点间距离double getDistance(point a, point b) { return (a - b).abs();}//点到直线距离double getDistanceLP(line l, point p) { return fabs((l.p1 - l.p2).det(p - l.p1)) / ((l.p2 - l.p1).abs());}//点到线段的距离double getDistanceSP(Segment s, point p) { if ((s.p2 - s.p1).dot(p - s.p1) < 0.0)return (p - s.p1).abs(); if ((s.p1 - s.p2).dot(p - s.p2) < 0.0)return (p - s.p2).abs();//!!!!! return getDistanceLP(s, p);}//判断线段p0p1与线段p0p2的旋转关系int ccw(point p0, point p1, point p2) { Vector a = p1 - p0; Vector b = p2 - p0; if (a.det(b) > EPS)return COUNTER_CLOCKWISE; if (a.det(b) < -EPS)return CLOCKWISE; if (a.dot(b) < -EPS)return ONLINE_BACK; if (a.norm() >= b.norm())return ON_SEGMENT;//!! return ONLINE_FRONT;}//判断线段p1p2与p3p4是否相交bool intersect(point p1, point p2, point p3, point p4) { return (ccw(p1, p2, p3)*ccw(p1, p2, p4) < 0 &&//!!! ccw(p3, p4, p1)*ccw(p3, p4, p2) < 0);}//线段是否相交bool intersect(Segment s1, Segment s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2);}typedef vector
                  
                   Polygon;bool judge_intersect(const Segment&a,const int&amount) { int y = a.p1.y, x1 = a.p1.x, x2 = a.p2.x; for (int i = 0; i 
                   
                     S_x[i].p1.y&&y < S_x[i].p2.y&&x1
                    
                     S_x[i].p2.x) { return true; } } return false;}int traverse(int&amount) { //返回总长度，不符条件-1 sort(P, P + n, cmp);//!!!!每次扫描前先排序 int count = 1, sum = 0; for (int i = 1; i < n; i++) { //遍历每一个点 if (P[i].get(is_x)!=P[i - 1].get(is_x)) { //到了新的扫描层 if (count & 1)return -1; count = 1; } else { count++; if (!(count & 1)) { sum += P[i].get(!is_x) - P[i - 1].get(!is_x); P[i].link(P[i - 1], is_x); if (is_x) { //若是横向扫描，直接记录连接好的线段 S_x[amount++]=Segment(P[i-1], P[i]); } else { //竖向扫描，判断当前连接线段是否和上面的记录的线段相交 if (judge_intersect(Segment(P[i-1],P[i]),amount)) { return -1; } } } } } return sum;}int solve() { int amount = 0;//记录连边的个数 is_x=1; int num_x = traverse(amount); if (num_x == -1)return -1;//!!!! is_x =0; int num_y = traverse(amount); if (num_y == -1)return -1; int loop = 0,count=0; do { //判断不联通的图 loop = is_x ? link_x[loop] : link_y[loop]; count++; is_x = !is_x; } while (loop != 0); if (count != n)return -1; return num_x + num_y;}int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) { int x, y; scanf("%d%d", &x, &y); P[i] = point(x, y, i); } printf("%d\n",solve()); } return 0;}