poj1113_code.cpp

问题：已经平面上的若干点

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
#define PI acos(-1.0)
#define maxn 1020
const double eps=1e-8;

struct point
{
	int x,y;
};
point ch[maxn];
int n,l,m;
point bp;
double sqr(double x)
{
	return x*x;
}
double dis(point p1,point p2)
{
	return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
double dissqr(point p1,point p2)
{
	return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);
}
int dcmp(double x)
{
	if(x<-eps)return -1;
	return (x>eps);
}
double cross(point p0,point p1,point p2)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dot(point p0,point p1,point p2)
{
	return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
bool polarcmp(point p1,point p2)
{
	int u=dcmp(cross(bp,p1,p2));
	return u>0||(u==0&&dcmp(dissqr(bp,p1)-dissqr(bp,p2))<0);
}
bool pointequal(point p1,point p2)
{
	return p1.x==p2.x&&p1.y==p2.y;
}
void GrahamScan()
{
	int i,j,k,u,v;
	for(i=k=0;i<n;i++)
	{
		u=dcmp(ch[i].x-ch[k].x);
		v=dcmp(ch[i].y-ch[k].y);
		if(v<0||(v==0&&u<0))k=i;
	}
	bp=ch[k];
	std::sort(ch,ch+n,polarcmp);
	n=std::unique(ch,ch+n,pointequal)-ch;
	if(n<=1)
	{
		m=n;return ;
	}
	if(dcmp(cross(ch[0],ch[1],ch[n-1]))==0)
	{
//		printf("%d here \n",n);
		m=2;
		ch[1]=ch[n-1];
		return ;
	}
	ch[n++]=ch[0];
	for(i=1,j=2;j<n;j++)
	{
		while(i>0&&dcmp(cross(ch[i-1],ch[i],ch[j]))<=0)i--;
		ch[++i]=ch[j];
	}
	m=i;
//	ch[m]=ch[0];
//	m++;
//	printf("%d %d \n",m,n);
	return ;
}

double angle(point p0,point p1,point p2)
{
	double cr=(p1.x-p0.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p1.y-p0.y);
	double dt=(p1.x-p0.x)*(p2.x-p1.x)+(p1.y-p0.y)*(p2.y-p1.y);
//	printf("%d %d %d %d %d %d %f %f %f\n",p0.x,p0.y,p1.x,p1.y,p2.x,p2.y,cr,dt,cr/dt);
	if(dcmp(cr)==0)cr=0.0;
	if(dcmp(dt)==0)dt=0.0;
	return atan2(cr,dt);
}
double shan()
{
	double ans=0;
	int i;
	for(i=0;i<m-2;i++)
	{
//		printf("%.2f \n",angle(ch[i],ch[i+1],ch[i+2]));
		
		ans+=l*(angle(ch[i],ch[i+1],ch[i+2]));
	}
	ans+=l*(angle(ch[m-2],ch[m-1],ch[0]));
	ans+=l*(angle(ch[m-1],ch[0],ch[1]));
	return ans;
}
int main()
{
//	printf("%.32f\n",acos(-1.0));
//	freopen("in.txt","r",stdin);
	double ans;
	int i;
//	while(scanf("%d%d",&n,&l)!=EOF)
//	{
		scanf("%d%d",&n,&l);
		for(i=0;i<n;i++)scanf("%d%d",&ch[i].x,&ch[i].y);
		GrahamScan();
//		printf("%d %d\n",n,m);
		ans=0;
		for(i=1;i<m;i++)ans+=dis(ch[i],ch[i-1]);
//		if(m==2)ans*=2;
//		for(i=0;i<m;i++)printf("%d %d\n",ch[i].x,ch[i].y);
		ans+=dis(ch[0],ch[m-1]);
//		printf("%.2f\n",ans);
		ans+=shan();
		printf("%.0f\n",ans);
//	}
	return 0;
}