题解 P3829 【[SHOI2012]信用卡凸包】

· · 题解

P3829 [SHOI2012]信用卡凸包

\color{silver}{\text{话说SH省选好良心，算法打在标题上}}

题意

给出若干个带圆弧的矩形，求凸包大小

题解

我们正常的凸包算法很显然只能做多边形所以三十分够了，而这个\dfrac 1 4圆就十分恶心。因此我们只能用\texttt{Oier}的祖传手艺（雾 —— 画图找规律了

首先我们拿出某软件，随手画一张图：

再画出其凸包：

经过观察我们发现，几条橙色的线段都与圆相切，那么我们如果把几个圆心与切点连接起来，就会得到一堆长方形和若干扇形，就像下图

那么\color{skyblue}{\text{蓝色虚线}}的长度就等于外圈线段的长度，又因为：

因此外面的弧的长度就等于一个圆的周长（证明很容易，但作为一名\texttt{Oier}我们完全可以不证明）

于是我们只要把所有的圆心丢进去跑一遍凸包就可以啦

代码

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
namespace Convex_Hull{
    #define sq(x) (x)*(x)
    struct node{
        double x,y;
    }p[1000000+1000],s[1000000+1000];
    int n=0,cnt;
    double check(node a1,node a2,node b1,node b2){
        return (a2.x-a1.x)*(b2.y-b1.y)-(a2.y-a1.y)*(b2.x-b1.x);
    }double d(node a,node b){
        return sqrt(sq(a.x-b.x)+sq(a.y-b.y));
    }bool cmp(node p1,node p2){
        double tmp=check(p1,p[1],p2,p[1]);
        if(tmp>0)return 1;
        else if(tmp==0&&d(p[0],p1)<d(p[0],p2))return 1;
        return 0;
    }
    void add(double x,double y){
        n++;
        p[n].x=x,p[n].y=y;
        if(p[n].y<p[1].y)swap(p[n],p[1]);
    }
    void deal(){
        sort(p+2,p+1+n,cmp);
        s[1]=p[1];cnt=1;
        for(int i=2;i<=n;i++){
            while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0)
                cnt--;
            s[++cnt]=p[i];
        }s[cnt+1]=p[1];
    }
    double C(){
        double ans=0;
        for(int i=1;i<=cnt;i++)
            ans+=d(s[i],s[i+1]);
        return ans;
    }
};
int n;double a,b,r;
double x,y,theta;
signed main(){
    scanf("%d%lf%lf%lf",&n,&a,&b,&r);
    a-=2*r;b-=2*r;
    double l=sqrt(a*a+b*b)/2;
    double phi=atan(a/b);
    while(n--){
        scanf("%lf%lf%lf",&x,&y,&theta);{
            double dx=cos(theta+phi)*l;
            double dy=sin(theta+phi)*l;
            Convex_Hull::add(x+dx,y+dy);
            Convex_Hull::add(x-dx,y-dy);

        }{
            double dx=cos(theta-phi)*l;
            double dy=sin(theta-phi)*l;
            Convex_Hull::add(x+dx,y+dy);
            Convex_Hull::add(x-dx,y-dy);
        }
    }Convex_Hull::deal();
    printf("%.2lf",Convex_Hull::C()+3.141592653589793*2*r);
    return 0;
}