1113 melkman.cpp

1113 melkman 凸包算法

// compute convex hull via melkman algorithm
// procondition: the original points' queue should be a simple polygonal chain
// O(n) using deque
#include <stdio.h>   
#include <string.h>   
#include <math.h>   
#include <stdlib.h>   
#define N 1024   
#define pi 3.141592653589793
struct node   
{   
	int x,y;
} P[N];    
//#define Make_Vector(p1,p2) (struct node){P[p2].x-P[p1].x, P[p2].y-P[p1].y}

  
int D[N*2],top,bot;   
int n,L;   

bool input()   
{   
	if (scanf("%d%d",&n,&L) != 2) return false;
	for (int i = 0;i < n; i++) scanf("%d%d",&P[i].x,&P[i].y);
	return true;
}   
	// v1 and v2 is two vector 
inline int crossP(struct node v1,struct node v2)//叉积   Cross Product
{   
	return v1.x * v2.y - v2.x * v1.y;
}   
inline struct node Make_Vector(int a,int b)
{
	struct node n;
	n.x = P[b].x - P[a].x; 
	n.y = P[b].y - P[a].y;
	return n;
}
int isleft(int p1,int p2,int p3)   
{   
	return crossP(Make_Vector(p1,p2),Make_Vector(p2,p3));   
}   
void convex_hull()   
{   int i;     
	D[top=n] = 0;	
	D[++top] = 1;   
	for (i = 2; i < n; i++) {   
		if (isleft(D[top-1],D[top],i) != 0) break;   
		D[top] = i;   
	}
	D[++top] = i;    
	D[bot=n-1] = i;   
	if (isleft(D[n],D[n+1],D[n+2]) < 0) {   
		int t = D[n]; D[n] = D[n+1]; D[n+1] = t;   
	}   
	for (++i; i < n; i++) {   
		if (isleft(D[bot],D[bot+1],i) > 0 && isleft(D[top-1],D[top],i) > 0) 
			continue;   
		while (isleft(D[top-1],D[top],i) <= 0) --top;   
		D[++top] = i;   
		while (isleft(D[bot],D[bot+1],i) <= 0) ++bot;   
		D[--bot] = i;   
	}   
}   
double length(int p1,int p2)   
{      
	double dx = P[p2].x - P[p1].x;   
	double dy = P[p2].y - P[p1].y;
	//printf("(%d,%d)\n",P[p1].x,P[p1].y);
	return sqrt(dx * dx + dy * dy);   
}   
void circumference()   
{       
	double ans = 2 * pi * L; 
	for (int i = bot; i < top; i++) {   
		ans += length(D[i],D[i+1]);  
	}   
	//printf("%.0lf\n",nearbyint(ans));   
	printf("%.0lf\n",ans); 
}   
int main()   
{   //freopen("in.txt","r",stdin);
	while (input()) {     
		convex_hull();   
		circumference();   
	}   
	return 0;   
}