P3829 题解

· · 题解

博客园食用

题目传送门

二维凸包模板传送门

题目分析

类似于凸包模板的一道题。

我们循序渐进地考虑，当半径 r=0 时，显然是一个二位凸包模板。

接着我们将圆弧加进去，仔细观察发现，我们构造出的凸包中的直线部分就是将圆心之间连起来的长度，而一个圆的贡献就是 \dfrac{1}{4} 个圆弧，四个圆贡献加起来正好就是一个圆的周长。

然后将模板改一下就做完了。

贴上代码

#include<bits/stdc++.h>
#define int long long
#define ok puts("Yes")
#define no puts("-1")
#define pi acos(-1)
#define at atan(A/B)
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
const int maxn=2e5+5;
const double eps=1e-18;
double equ(double x){
    if(fabs(x)<eps) return 0;
    if(x>=0) return 1;
    else return -1;
}
int n;
int cnt;
double a,b,r,x,y,op;
double A,B,C;
double ans;
struct point{
    double x,y;
    point(double _x=0,double _y=0):x(_x),y(_y){}
    point operator + (const point &pt){return point(x+pt.x,y+pt.y);}
    point operator - (const point &pt){return point(x-pt.x,y-pt.y);}
}p[maxn];
bool cmp(point p,point q){
    if(equ(p.x-q.x)==0) return p.y<q.y;
    else return p.x<q.x;
}
struct my_stack{
    point stk[maxn];int sz=0;
    void push(point x){stk[sz++]=x;}
    point top(){return stk[sz-1];}
    point sec_top(){return stk[sz-2];}
    int size(){return sz;}
    void pop(){sz--;}
}st;
// bool slope(int aa,int b,int c){return (p[aa].y-p[b].y)*(p[b].x-p[c].x)>(p[aa].x-p[b].x)*(p[b].y-p[c].y);}
double dis(point a,point b){return sqrt((a.y-b.y)*(a.y - b.y)+(a.x-b.x)*(a.x-b.x));}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double len(point a){return sqrt(dot(a,a));}
double angle(point a,point b){return acos(dot(a,b)/len(a)/len(b));}
inline void init(){
    n=read();
    scanf("%lf%lf%lf",&a,&b,&r);
    A=a-2.0*r;B=b-2.0*r;C=sqrt(A*A+B*B)/2.0;
    for(register int i=1;i<=n;++i){
        scanf("%lf%lf%lf",&x,&y,&op);
        double xx=cos(op+at)*C,yy=sin(op+at)*C;
        p[++cnt].x=x+xx;p[cnt].y=y+yy;
        p[++cnt].x=x-xx;p[cnt].y=y-yy;
        xx=cos(op-at)*C,yy=sin(op-at)*C;
        p[++cnt].x=x+xx;p[cnt].y=y+yy;
        p[++cnt].x=x-xx;p[cnt].y=y-yy;
    }
    sort(p+1,p+cnt+1,cmp);
}
signed main(){
    init();
    for(register int i=1;i<=cnt;++i){
        while(equ(cross(st.top()-st.sec_top(),p[i]-st.sec_top()))==-1&&st.size()>1) st.pop();
        st.push(p[i]);
    }
    int siz=st.size();
    for(register int i=cnt-1;i>=1;--i){
        while(equ(cross(st.top()-st.sec_top(),p[i]-st.sec_top()))==-1&&st.size()>siz) st.pop();
        st.push(p[i]);
    }
    for(register int i=0;i<st.size()-1;++i) ans+=dis(st.stk[i],st.stk[i+1]);
    ans+=2.0*pi*r;
    printf("%.2lf",ans);
}