[ACM_几何] Wall

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28417#problem/E

题目大意：依次给n个点围成的一个城堡，在周围建围墙，要求围墙离城墙的距离大于一定的值，求围墙最短长度（结果四舍五入

解题思路：求围住所有点的凸包周长+一个圆的周长

#include<iostream>

#include<cmath>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<iomanip>

using namespace std;

#define eps 0.0000000001

#define PI acos(-1.0)

//*******************************************************************************

//点和向量

struct Point{

    double x,y;

    Point(double x=,double y=):x(x),y(y){}

};

typedef Point Vector;

Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}

bool operator<(const Vector& a,const Vector& b){return a.x<b.x||(a.x==b.x && a.y<b.y);}

int dcmp(double x){

    if(fabs(x)<eps)return ;

    else return x< ? -:;

}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//向量点积

double Length(Vector A){return sqrt(Dot(A,A));}//向量模长

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

//********************************************************************************

//计算凸包输入点数组p，个数n，输出点数组ch，返回凸包定点数

//输入不能有重复，完成后输入点顺序被破坏

//如果不希望凸包的边上有输入点，把两个<=改成<

//精度要求高时，建议用dcmp比较

//基于水平的Andrew算法-->1、点排序2、删除重复的然后把前两个放进凸包

//3、从第三个往后当新点在凸包前进左边时继续，否则一次删除最近加入的点，直到新点在左边

int ConVexHull(Point* p,int n,Point*ch){

    sort(p,p+n);

    int m=;

    for(int i=;i<n;i++){//下凸包

        while(m> && Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=)m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-;i>=;i--){//上凸包

        while(m>k && Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=)m--;

        ch[m++]=p[i];

    }

    if(n>)m--;

    return m;

}

//*******************************************************************

int main(){

    int n,L;

    while(cin>>n>>L){

        Point p[],ch[];

        for(int i=;i<n;i++)  //输入点

            cin>>p[i].x>>p[i].y;

        int m=ConVexHull(p,n,ch);   //求解凸包并计算凸包周长

        double sum=Length(ch[]-ch[m-]);

        for(int i=;i<m;i++)

            sum+=Length(ch[i]-ch[i-]);

        printf("%.0lf\n", sum+*L*PI);//输出周长+圆周并四舍五入

    }

    return ;

}