» » Convex Hull (Grahm Scan)

Convex Hull (Grahm Scan)

   7:47 PM       

 
point fp;
bool cmp(const point &a,const point &b){
	i64 d = isLeft(fp,a,b);
	if(d<0)return false;
	if(feq(d,(i64)0) && (dist(fp,a) > dist(fp,b)) )return false;
	return true;
}
void ConvexHull(point p[], point c[], int &np, int &nc){
	int i,j,pos = 0,k;
	i64 dd;
	bool flg=0;
	for(i=1;i<np;i++){
		if( (p[i].x < p[pos].x) || ( feq(p[i].x,p[pos].x) && p[i].y < p[pos].y) )pos = i;
		dd = isLeft(p[0],p[i],p[(i+1)%np]);
		if(!flg && !feq(dd,(i64)0))flg=1;
	}
	swap(p[pos],p[0]);
	fp = p[0];
	sort(p+1,p+np,cmp);
	c[0] = p[0];
	c[1] = p[1];
	c[2] = p[2];
	for(i = j = 3; i < np; i++){
		while(isLeft(c[j-2],c[j-1],p[i]) < 0)j--;
		c[j++] = p[i];
	}
	i--;
	for(k=i-1;k>=0 && flg;k--){
		dd = isLeft(c[0],p[k],p[i]);
		if(!feq(dd,(i64)0))break;
		c[j++] = p[k];
	}
	if(np>2)nc = j;
	else nc = np;
}
inline i64 PolygonArea(point p[],int np){
	i64 area = 0;
	for(int i = 0;i < np; i++){
		area += ( (p[i].x*p[(i+1)%np].y) - (p[i].y*p[(i+1)%np].x) );
	}
	return area;
}