poj 1113 Wall-----凸包

凸包问题。

先按 x坐标排序，x一样的按 y 排序。

取p【0】为开始点，每个点与开始点相连，按x轴正方向，每条线段与x轴的夹角 由小到大排序。

然后选点求距离。。。

本题求凸包的边长+以L为半径的园的周长。

//自己的凸包模板
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define pi acos(-1.0)
#define N 100100
#define inf 0x3f3f3f3f

struct node
{
	double x,y;
}p[100100];
int s[100100];
double dis(node a,node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double chaji(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b)
{
	a.x-=p[0].x,a.y-=p[0].y;
	b.x-=p[0].x,b.y-=p[0].y;
	if(chaji(a,b)==0)
		return a.x<b.x;
	return (chaji(a,b)>0);
}
int main()
{
	int n,r;
	while(~scanf("%d%d",&n,&r))
	{
		int i,j,k,t=-1;
		for(i=0;i<n;++i){
			scanf("%lf%lf",&p[i].x,&p[i].y);
			if(t==-1 || p[i].x<p[t].x)
				t=i;
			else if(p[i].x==p[t].x && p[i].y<p[t].y)
				t=i;
		}
		if(n==1)
		{
			printf("%.2lf\n",2*pi*r);
		}
		else if(n==2)
		{
			printf("%.2lf\n",2*pi*r+dis(p[0],p[1])*2);
		}
		else
		{
			node tt;
			tt=p[t],p[t]=p[0],p[0]=tt;
			sort(p+1,p+n,cmp);
			int ans=0;
			s[0]=0,s[1]=1,ans+=2;
			for(i=2;i<n;i++)
			{
				if(ans<=1)
					s[ans]=i,ans++;
				else
				{
					node a,b;
					k=ans;
					a.x=p[s[k-2]].x-p[s[k-1]].x;
					a.y=p[s[k-2]].y-p[s[k-1]].y;
					b.x=p[s[k-1]].x-p[i].x;
					b.y=p[s[k-1]].y-p[i].y;
					if(chaji(a,b)>=0)
						s[ans]=i,ans++;
					else{
						ans--;
						i--;
					}
				}
			}
			double sum=0;
			for(i=1;i<ans;i++)
				sum+=dis(p[s[i]],p[s[i-1]]);
			sum+=dis(p[s[ans-1]],p[s[0]]);
			printf("%.0lf\n",sum+2*pi*r);
		}
	}
}