凸包.cpp

各种算法

//convex hull algorithm of Graham
#include"iostream"
#include"stdio.h"
//#include"stdlib.h"
#include"math.h"
#include"algorithm"
#include"stack"
using namespace std;
#define N 1002
#define INF (unsigned int)(-1)>>1
#define PI 3.1415926

typedef struct TPoint
{
    double x;
    double y;
    //double z;
	TPoint(){}
	TPoint(double a,double b){x = a; y = b;}
}TPoint;	
TPoint v[N];
int n;int r;					// 3<=n<=1000
enum orientation{ _left = -1,straight = 0,_right = 1};

int cross(TPoint m,TPoint n)
{
	if(n.x*m.y - m.x*n.y > 0) return _right;
	else if (n.x*m.y - m.x*n.y == 0) return straight;
	else return _left;
}
int direction(TPoint a,TPoint b,TPoint c)//Cross Funtion 叉积
{	TPoint m,n;
	m.x = b.x - a.x;
	m.y = b.y - a.y;
	n.x = c.x - a.x;
	n.y = c.y - a.y;
	return cross(m,n);
}
bool cmp(TPoint a,TPoint b)
{	
	TPoint o = v[0];
	TPoint c,d;
	c.x = a.x-o.x;
	d.x = b.x-o.x;
	c.y = a.y-o.y;
	d.y = b.y-o.y;
	if(cross(c,d) == _right) return true;
	else if (cross(c,d) == straight){
		if(c.x*c.x+c.y*c.y - (d.x*d.x+d.y*d.y)<0) return true;
		else return false;
	}
	else return false;
}
void Sort()//求逆时针扇形阵列
{	
	for(int i = 1; i < n; i++) //find start point
		if(v[i].y < v[0].y||(v[i].y == v[0].y && v[i].x < v[0].x))
			swap(v[i],v[0]);
	sort(v+1,v+n,cmp);
}
stack<TPoint>Graham()
{	
	stack<TPoint>st;	
	TPoint tmp = v[1]; v[n] = v[0];
	st.push(v[0]);
	for(int i = 2;i <= n;i++){
		while(direction(st.top(),tmp,v[i]) == _left){
			tmp = st.top(); st.pop();
		}
		if(direction(st.top(),tmp,v[i]) == _right) st.push(tmp); // =0 斜率相同 排除		
		tmp = v[i];
	}
	return st;
}
double length(TPoint p,TPoint q)
{	return sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2));
}
bool input()
{	
	if(scanf("%d%d",&n,&r) == EOF) return false;
	for(int i = 0;i < n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
	return true;
}
double circumference(stack<TPoint>st)
{	
	double sum = 0;
	TPoint head = st.top();
	TPoint p = head; st.pop();
	while(!st.empty())
	{	//printf("(%.1f,%.1f)\n",p.x,p.y);
		TPoint q = st.top();
		sum += length(p,q);
		st.pop(); p = q;
	}
	sum += length(head,p) + PI * 2 * r;
	return sum;
}
int main()
{	freopen("in.txt","r",stdin);
	while(input()) {
		Sort();
		stack<TPoint>st = Graham();	
		printf("%.0lf\n",circumference(st));
	}
	return 1;
}

/*
7 7
0 0
1 1
4 4
2 2
3 3
2 4
0 5
*/