バンプ-graham-scanアルゴリズム

(1)質問:
2 D平面点セットを指定し、すべての点を含む凸多角形を最小にします.
(2)Gramham-Scanアルゴリズム:
Gramham−Scanは柔軟なバンプアルゴリズムであり,その全時間複雑度はO(n*log(n))にすぎない.
手順:
Step 1:x座標が最小(同じ場合yが最小)の点を極点として選択し、この点は必ず凸包にある.
Step 2:残りの点を極角で並べ替え、極角が同じ場合に極点との距離を比較し、極点に近いものを優先する.
Step 3:凸包上の点を1つのスタックSで格納し、極角と極点で並べ替えた最小の2つの点をスタックに入れる.
Step 4:各点を順番にスキャンし、スタックの上部の2つの要素とこの点からなる折れ線セグメントが右側に「曲がる」かどうかを確認します(フォーク積がゼロ以下).
Step 5:満足している場合はスタックトップ要素をポップアップし、満足しないまでStep 4に戻って再度チェックします.ポイントをスタックに入れ、残りのポイントに対してこの操作を継続します.
Step 6:最終スタックの要素はバンプの頂点シーケンスです.
(3)テンプレート(kuangbinテンプレートより)

#include 
#include 
#include 
#include 
using namespace std;

const double eps = 1e-8;
struct Point{
    double x, y;
};

const int MAXN = 1010;
Point list[MAXN];
int stack[MAXN], top;

/***
*   
* a×b>0,  b a      ；
* a×b<0,  b a      ；
* a×b=0,  a b  ，          。
*/
double crossProduct(Point a, Point b){
	return a.x*b.y - a.y*b.x;
}

int sgn(double x){
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	else return 1;
}

Point sub(Point a, Point b){
	Point p;
	p.x = a.x - b.x;
	p.y = a.y - b.y;
	return p;
}

double dist(Point a, Point b){
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

//     list[0]     
bool cmp(Point p1, Point p2){
    double temp  = crossProduct(sub(p1, list[0]), sub(p2, list[0]));
	if(sgn(temp)>0) return true;
	else if(sgn(temp)==0 && sgn(dist(p1, list[0])-dist(p2, list[0]))<=0) return true;
	else return false;
}

/*
*    ，Graham  
*     0~n-1
*       Stack[0~top-1]      
*/
void Graham(int n){
    Point p0 = list[0];
    int k = 0;
    for(int i=1;ilist[i].y || (p0.y==list[i].y && p0.x>list[i].x)){
            p0 = list[i];
            k = i;
        }
    }
    swap(list[k], list[0]);
    sort(list+1, list+n, cmp);

	stack[0] = 0;
    if(n==1){top = 1; return;}
    stack[1] = 1;
    if(n==2){top = 2; return;}

	top = 2;
	for(int i=2;i1 && sgn(crossProduct(sub(list[stack[top-1]], list[stack[top-2]]), sub(list[i], list[stack[top-2]])))<=0){
			top--;
        }
        stack[top++] = i;
	}
}