melkman.cpp

melkman code 多边形求凸包的算法

#include <stdio.h>
#include <string.h>
#include <math.h>

#define SQR(x) ((x)*(x))

int n;
struct point
{
	double x, y;
}P[128], tmp[128];
int deque[256];

double det(double x1, double y1, double x2, double y2)
{
	return x1*y2 - x2*y1;
}

double cross(point p1, point p2, point p3)
{
	return det(p2.x-p1.x, p2.y-p1.y, p3.x-p2.x, p3.y-p2.y);
}

bool cmp(point p1, point p2)
{
	if(p1.y > p2.y)   
		return true;
	else if(p1.y < p2.y)
		return false;
	else
		return p2.x < p1.x;
}

void MergeSort(int from, int to)
{
	if(to - from == 1) return ;
	if(to - from == 2)
	{
		if(cmp(P[from], P[from+1]))
		{
			point t = P[from];
		    P[from] = P[from+1];
			P[from+1] = t;
		}
		return ;
	}

	int mid = (from+to)/2;
	MergeSort(from, mid);
	MergeSort(mid, to);

	int p1 = mid - from - 1, p2 = to - mid - 1, p = to - from;
	while(p1 >= 0 && p2 >= 0)
	{
		if(cmp(P[from+p1], P[mid+p2]))
			tmp[--p] = P[from + p1--];
		else
		    tmp[--p] = P[mid + p2--];
	}
	while(p1 >= 0)
		tmp[--p] = P[from + p1--];
	while(p2 >= 0)
		tmp[--p] = P[mid + p2--];

	memcpy(&P[from], tmp, (to - from)*sizeof(struct point));
	return ;
}

int main()
{
	while(scanf("%d", &n), n)
	{
		for(int i=1;i<=n;++i)
			scanf("%lf %lf", &P[i].x, &P[i].y);
		MergeSort(1, n+1);
		//m_sort(1, n);

        // start convex-hull process
		int p1 = 99,  p2 = 101;   // left and right pointer
		deque[p1] = 1;  deque[p1+1] = 2;  deque[p2] = 3;
		if(cross(P[1], P[2], P[3]) < 0) { deque[p1] = 2;  deque[p1+1] = 1; }
		deque[--p1] = 3; 

        // deal with small-n case
        if(n == 1) 
		{ 
			printf("0.00\n");
			continue; 
		} 
		if(n == 2)
		{ 
			printf("%.2lf\n", 2*sqrt(  SQR(P[2].x - P[1].x)
				        + SQR(P[2].y - P[1].y))  ); 
			continue; 
		} 

        double t;
		for(int i=4;i<=n;++i)
		{
			deque[--p1] = i;
			t = cross(P[deque[p1+2]], P[deque[p1+1]], P[deque[p1]]);
			while(t > 0)   // if not left hand sys
			{
				deque[p1+1] = deque[p1];
				++p1;
				t = cross(P[deque[p1+2]], P[deque[p1+1]], P[deque[p1]]);
			}

			deque[++p2] = i;
		    t = cross(P[deque[p2-2]], P[deque[p2-1]], P[deque[p2]]);
			while(t < 0)   // if not right hand sys
			{
				deque[p2-1] = deque[p2];
				--p2;
				t = cross(P[deque[p2-2]], P[deque[p2-1]], P[deque[p2]]);
			}
		}

        double length = 0;
		for(int i=p1+1;i<=p2;++i)
			length += sqrt(  SQR(P[deque[i]].x - P[deque[i-1]].x)
				        + SQR(P[deque[i]].y - P[deque[i-1]].y)  );
		printf("%.2lf\n", length);

		//for(int i=0;i<=n;++i) printf("%.0lf %.0lf\n", P[i].x, P[i].y); printf("\n");
	}
	return 0;
}