POJ 1113 Wall

题意：给一个多边形的城堡，要给城堡建一个围墙，要求围墙对每面墙的距离都不少于l，且用料最少，需要建多长的围墙。

解法：嗯……其实一开始并没太读懂题意……不过大家都说题意就是求个凸包……那就求凸包吧。围墙的直线部分就是一个城堡的凸包，所有的角合起来是一个半径为l的圆周。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
#define Vector Point

using namespace std;

const double eps = 1e-6;
int dcmp(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); }
struct Point {
    double x, y;

    Point(const Point& rhs): x(rhs.x), y(rhs.y) { } //拷贝构造函数
    Point(double x = 0.0, double y = 0.0): x(x), y(y) { }   //构造函数

    friend istream& operator >> (istream& in, Point& P) { return in >> P.x >> P.y; }
    friend ostream& operator << (ostream& out, const Point& P) { return out << P.x << ' ' << P.y; }

    friend Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); }
    friend Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); }
    friend Vector operator * (const Vector& A, const double& p) { return Vector(A.x*p, A.y*p); }
    friend Vector operator / (const Vector& A, const double& p) { return Vector(A.x/p, A.y/p); }
    friend bool operator == (const Point& A, const Point& B) { return dcmp(A.x-B.x) == 0 && dcmp(A.y-B.y) == 0; }
    friend bool operator < (const Point& A, const Point& B) { return A.x < B.x || (A.x == B.x && A.y < B.y); }

    void in(void) { scanf("%lf%lf", &x, &y); }
    void out(void) { printf("%lf %lf", x, y); }
};
typedef vector<Point> Polygon;
double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; }  //点积
double Length(const Vector& A){ return sqrt(Dot(A, A)); }
double Angle(const Vector& A, const Vector& B) { return acos(Dot(A, B)/Length(A)/Length(B)); }  //向量夹角
double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; }    //叉积
double Area(const Point& A, const Point& B, const Point& C) { return fabs(Cross(B-A, C-A)); }

Polygon ConvexHull(vector<Point> p) {
    //预处理，删除重复点
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size(), m = 0;
    Polygon res(n+1);
    for(int i = 0; i < n; i++) {
        while(m > 1 && Cross(res[m-1]-res[m-2], p[i]-res[m-2]) <= 0) m--;
        res[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i--) {
        while(m > k && Cross(res[m-1]-res[m-2], p[i]-res[m-2]) <= 0) m--;
        res[m++] = p[i];
    }
    m -= n > 1;
    res.resize(m);
    return res;
}
int main()
{
    int n, l;
    while(~scanf("%d%d", &n, &l))
    {
        vector <Point> v;
        for(int i = 0; i < n; i++)
        {
            double x, y;
            scanf("%lf%lf", &x, &y);
            v.push_back(Point(x, y));
        }
        Polygon p = ConvexHull(v);
        int len = p.size();
        double ans = 0.0;
        for(int i = 0; i < len; i++)
            ans += Length(Point(p[i].x - p[(i + 1) % len].x, p[i].y - p[(i + 1) % len].y));
        ans += l * 2 * acos(-1.0);
        printf("%d
", (int)(ans + 0.5));
    }
    return 0;
}