POJ 1228 凸包惟一性判断（多边形模板）

Description

Input

Output

Sample Input

1
6 
0 0
1 2
3 4
2 0
2 4 
5 0

Sample Output

NO

题意：判断凸包是否惟一。

思路：把凸包的结点先变成顶点，然后再判断两个顶点之间是否还有结点，如果有顶点，说明两个顶点之间的边是惟一的。如果顶点之间没有结点，所以这两个顶点之间可以有其他加入的结点让这个凸包不惟一。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAX 111116 #define eps 1e-7 using namespace std; int sgn(const double &x){ return x < -eps  -1 : (x > eps);} inline double sqr(const double &x){ return x * x;} inline int gcd(int a, int b){ return !b  a: gcd(b, a % b);} struct Point { double x, y; Point(const double &x = 0, const double &y = 0):x(x), y(y){} Point operator -(const Point &a)const{ return Point(x - a.x, y - a.y);} Point operator +(const Point &a)const{ return Point(x + a.x, y + a.y);} Point operator *(const double &a)const{ return Point(x * a, y * a);} Point operator /(const double &a)const{ return Point(x / a, y / a);} bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);} bool operator == (const Point &a)const{ return sgn(sgn(x - a.x) == 0 && sgn(y - a.y) == 0);} friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;} friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;} friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} void in(){ scanf("%lf %lf", &x, &y); } void out()const{ printf("%lf %lf\n", x, y); } }; struct Line //线段类 { Point s, t; Line() {} Line(const Point &s, const Point &t):s(s), t(t) {} void in() { s.in(),t.in(); } double pointDistLine(const Point &p) { if(sgn(dot(t - s, p - s)) < 0)return dist(p, s); if(sgn(dot( s - t, p - t)) < 0)return dist(p, t); return fabs(det(t - s, p - s)) / dist(s, t); } bool pointOnLine(const Point &p) { return sgn(det(s - p, t - p)) == 0 && sgn(dot(s - p, t - p)) < 0; } }; struct Poly //多边形类 { vector
       
        a; vector
        
         p; //顺时针凸包 vector
         
          tb;// 逆时针凸包 void in(const int &r) { p.resize(r); //不早凸包的时候可以把p改为a for(int i = 0; i < r; i++) p[i].in(); } //计算多边形的周长 double perimeter() { double sum=0; int n=a.size(); for(int i=0;i
          
           0&&d1<=0&&d2>0) num++; if(k<0&&d2<=0&&d1>0) num--; } return num!=0; } //计算多边形边界的格点数 int border() { int num=0,i,n=a.size(); for(i=0;i
           
             1 && sgn(det(tb[m - 1] - tb[m - 2], p[i] - tb[m - 2])) <= 0)m--; tb[m++] = p[i]; } int k = m; for(int i = n - 2; i >= 0; i--) { while(m > k && sgn(det(tb[m - 1] - tb[m -2], p[i] - tb[m - 2])) <= 0)m--; tb[m++] = p[i]; } tb.resize(m); if(m > 1)tb.resize(m - 1); //for(int i = 0; i < m - 1; i++) tb[i].out(); } //判断点t(圆心)是否在凸包内部，这个是O(logn)的算法 bool isContainOlogn(const Point &t) { int n = tb.size(); if(n < 3)return 0; Point g = (tb[0] + tb[n / 3] + tb[n * 2 / 3] )/ 3.0; int l = 0, r = n; while(l + 1 < r) { int mid = (l + r) >> 1; int k = sgn(det(tb[l] - g, tb[mid] - g) ); int dl = sgn(det(tb[l] - g, t - g) ); int dr = sgn(det(tb[mid] - g, t - g) ); if(k > 0) { if(dl >= 0 && dr < 0) r = mid; else l = mid; } else { if(dl < 0 && dr >= 0) l = mid; else r = mid; } } r %= n; int res = sgn(det(tb[l] - t, tb[r] - t)); if(res >= 0) return true; return false; } //判断凸包是否惟一,若顶点之间有点说明惟一 bool isUnique() { if(sgn(getArea()) == 0) return false; int n = tb.size(); int np = p.size(); for(int i = 0; i < n; i++) { Line line(tb[i], tb[(i + 1) % n]); bool isFind = false; for(int j = 0; j < np; j++) { if(line.pointOnLine(p[j])) { isFind = true; break; } } if(!isFind) return false; } return true; } }poly; int main() { int T; cin>>T; while(T--) { int n; cin>>n; poly.in(n); poly.isCanHull(); if(poly.isUnique()) puts("YES"); else puts("NO"); } return 0; }