题意:给出一个多边形,在距离这个多边形最低为L的地方建立一堵墙,求这墙的周长。

题解:对圆角加起来为什么是个圆很不理解,所以就看了kuangbin巨巨的题解。

这道题的答案是凸包周长加上一个圆周长,即包围凸包的一个圆角多边形,但是没弄明白那些圆角加起来为什么恰好是一个圆。每个圆角是以凸包对应的顶点为圆心,给定的L为半径,与相邻两条边的切点之间的一段圆弧。每个圆弧的两条半径夹角与对应的凸包的内角互补。假设凸包有n条边,则所有圆弧角之和为180°*n-180°*(n-2)=360°。故,围墙周长为=n条平行于凸包的线段+n条圆弧的长度=凸包周长+围墙离城堡距离L为半径的圆周长。


代码:

StatusAccepted
Time16ms
Memory860kB
Length2362
LangG++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps=1e-12;
const double pi=acos(-1.0);
int dcmp(double x){ if(fabs(x)<eps)return 0;else return x<0?-1:1;}
struct Point{
    int id;
    double x, y;
    Point(){}
    Point(double _x, double _y){x=_x,y=_y;}
    void input(){scanf("%lf%lf", &x, &y);}
    void output(){printf("%.2lf %.2lf\n", x, y);}
    bool operator==(const Point &p)const{return dcmp(x-p.x)==0 && dcmp(y-p.y)==0;}
    bool operator <(const Point &p)const{return dcmp(x-p.x)==0?dcmp(y-p.y)<0:x<p.x;}
    double operator ^(const Point &p)const{return x*p.y-y*p.x;} //叉积
    double operator *(const Point &p)const{return x*p.x+y*p.y;} //点积
    Point operator +(const Point &p)const{return Point(x+p.x, y+p.y);}
    Point operator -(const Point &p)const{return Point(x-p.x, y-p.y);}
    Point operator *(const double &k)const{return Point(x*k, y*k);}
    Point operator /(const double &k)const{return Point(x/k, y/k);}
    double len(){return sqrt(x*x+y*y);}                         //长度
    double len2(){return x*x+y*y;}                              //长度的平方
    double distance(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));} //距离
};
vector<Point> getConvexHull(vector<Point> res){
    vector<Point> ans;
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    int cnt=0;
    for(int i=0;i<res.size();i++){
        while(cnt>1 && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--;
        ans.push_back(res[i]),cnt++;
    }
    int s=cnt;
    for(int i=int(res.size())-2;i>=0;--i){
        while(cnt>s && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--;
        ans.push_back(res[i]),cnt++;
    }
    if(cnt>1)ans.pop_back();
    return ans;
}
int N, L;
int main(){
    while(~scanf("%d%d", &N, &L)){
        vector<Point> res;
        Point p;
        for(int i=0;i<N;i++){
            scanf("%lf%lf", &p.x, &p.y);
            p.id=i+1;
            res.push_back(p);
        }
        vector<Point> ans=getConvexHull(res);
        double sum=pi*L*2;
        for(int i=1;i<ans.size();i++){
            sum+=ans[i-1].distance(ans[i]);
        }
        sum+=ans[0].distance(ans[ans.size()-1]);
        printf("%.0f\n", sum);
    }
    return 0;
}