Graham Scan

1.找左下角点p[0] 

2.以p[0]为C极角排序（叉积 同角度 dis取min）

3.遍历叉积判断p[i]加进凸包队列后前面哪些点pop

可以保证在最差情况下也能在O(nlogn)的时间复杂度求出结果 

凸包面积：叉积（三角形面积）

凸包周长：直接dis

#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> using namespace std; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const int MaxN = 1e3 + 5; int n,Top; double L,Cir; struct Point{ double x,y; Point(double x = 0,double y = 0) : x(x),y(y) {} }stack[MaxN],C,a[MaxN]; typedef Point Vector; int dcmp(double x){//equal ?= 0 if(fabs(x) < eps) return 0; else return x < 0 ? -1:1; } //运算符重载 Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); } Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x, A.y-B.y); } Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); } bool operator == (const Point &a, const Point &b){ return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; } double Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; } double dis(Point A,Point B){ return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); } //叉积极角排序 double compare(Point a,Point b,Point c){ return Cross(c - a,c - b);//a在b顺时针 >0 } bool cmp(Point a,Point b){ if(dcmp(compare(a,b,C)) == 0) return dis(a,C) < dis(b,C);//短的在前 return dcmp(compare(a,b,C)) > 0; } //Graham_scan凸包扫描 void Graham_scan(Point p[]){ int i,k = 0; Top = 2; for(i = 1;i < n; i++){ if(p[i].y < p[k].y || (p[i].y == p[k].y && p[i].x < p[k].x)) k = i; } swap(p[0],p[k]);//p[0]是左下角点 C = p[0]; //按极角从小到大，距离偏短进行排序 sort(p + 1,p + n,cmp); stack[0] = p[0]; stack[1] = p[1]; stack[2] = p[2]; for(int i = 3;i < n; i++){ while(Top > 1 && dcmp(compare(p[i],stack[Top],stack[Top - 1])) >= 0) Top--; stack[++Top] = p[i]; } } double get_S_Graham(){ double ans = 0.0; for(int i = 1;i < Top;i++){ ans += Cross(stack[i] - stack[0],stack[i + 1] - stack[0]); } ans /= 2.0; return ans; }

poj1228 判断一个凸包是不是稳定凸包

感觉这个题数据有点水 稳定凸包共线的情况极角排序哪里似乎不太对？看了很多网上的代码也都一毛一样 

这里有一组数据可以参考一下：

9 0 0 1 0 2 0 2 1 2 2 0 2 0 1 1 3 0 4  

#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> using namespace std; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const int MaxN = 1e3 + 5; int n,Top,t; double L,Cir; struct Point{ double x,y; Point(double x = 0,double y = 0) : x(x),y(y) {} }stack[MaxN],C,a[MaxN]; typedef Point Vector; int dcmp(double x){//equal ?= 0 if(fabs(x) < eps) return 0; else return x < 0 ? -1:1; } //运算符重载 Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); } Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x, A.y-B.y); } Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); } bool operator == (const Point &a, const Point &b){ return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; } double Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; } double dis(Point A,Point B){ return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); } //叉积极角排序 double compare(Point a,Point b,Point c){ return Cross(c - a,c - b);//a在b顺时针 >0 } bool cmp(Point a,Point b){ if(dcmp(compare(a,b,C)) == 0) return dis(a,C) < dis(b,C);//短的在前 return dcmp(compare(a,b,C)) > 0; } //Graham_scan凸包扫描 void Graham_scan(Point p[]){ int i,k = 0; Top = 2; for(i = 1;i < n; i++){ if(p[i].y < p[k].y || (p[i].y == p[k].y && p[i].x < p[k].x)) k = i; } swap(p[0],p[k]);//p[0]是左下角点 C = p[0]; //按极角从小到大，距离偏短进行排序 sort(p + 1,p + n,cmp); stack[0] = p[0]; stack[1] = p[1]; stack[2] = p[2]; for(int i = 3;i < n; i++){ while(Top > 1 && compare(p[i],stack[Top],stack[Top - 1]) > 0) Top--; stack[++Top] = p[i]; } } bool convex_Stable(){ stack[Top + 1] = stack[0]; for(int i = 1;i < Top; i++){ if(compare(stack[i + 1],stack[i],stack[i - 1]) && compare(stack[i + 2],stack[i + 1],stack[i])) return false; } // if(compare(stack[0],stack[Top],stack[Top - 1]) || compare(stack[0],stack[1],stack[2])) return 0; return true; } bool Collinear(){ Point P = a[0]; int cnt = 0,C = 0; for(int i = 1;i < n; i++){ for(int j = i + 1;j < n; j++){ double A = Cross(P - a[i],P - a[j]); C++; if(!dcmp(A)) cnt++; } } return C != cnt; } int main() { scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 0;i < n; i++){ scanf("%lf %lf",&a[i].x,&a[i].y); } if(n < 6){ printf("NO\n"); continue; } Graham_scan(a); if(convex_Stable() && Collinear()) printf("YES\n"); else printf("NO\n"); } }