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

· · 题解

题目大意

求带圆弧卡片的凸包（凸包包含圆弧）。

关于点的旋转

设当前点为 A(x,y)，将其绕原点 O 逆时针旋转 \theta^\circ 得点 A'，则 A'(x\ \cos\ \theta^\circ-y\ \sin\ \theta^\circ,y\ \cos\ \theta^\circ+x\ \sin\ \theta^\circ)。

转化

如果我们知道了圆弧如何表示（或者知道圆弧总长为定值），就可以开始乱搞计算一般多边形的凸包了。

结论：最终凸包的圆弧总长恰好等于一个给定半径为 r 的圆的周长。

证明：

[![UlsSAK.png](https://s1.ax1x.com/2020/07/11/UlsSAK.png)](https://imgchr.com/i/UlsSAK) $\quad$那么对于多边形的角 $\alpha_i$，对应的圆心角 $\beta_i$，有 $\alpha_i+\beta_i=180^\circ$。 $\quad$多边形内角和为：$\sum_{i=1}^n\alpha_i=180(n-2)^\circ$。 $\quad\therefore \sum_{i=1}^n\beta_i=180n^\circ-180(n-2)^\circ=360^\circ=2\pi$。即证。 接下来，我们除去圆弧将剩下的直边进行平移，由之前的结论可证四边形 $OBDE$ 为矩形，于是平移后就转化成了求各个圆心的凸包。 所以答案即为一个圆的周长+圆心构成的凸包的周长。 $Code: 
#include<bits/stdc++.h>
#define db double 
#define N 100005
const db pi=acos(-1);
struct point{
    db x,y;
    point(db _x=0,db _y=0):x(_x),y(_y){}
    inline point operator-(const point&p)const{
        return point(x-p.x,y-p.y);
    }
    inline point operator+(const point&p)const{
        return point(x+p.x,y+p.y);
    }
    inline db dis(){return x*x+y*y;}
} p[N],sta[N];
inline db dist(point a,point b){return sqrt((a-b).dis());}
inline db cross(point a,point b,point c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
inline bool cmp(point a,point b){
    db tmp=cross(p[1],a,b);
    if(tmp>0) return 1;
    if(tmp==0&&dist(p[0],a)<dist(p[0],b)) return 1;
    return 0;
}
inline point rotate(point p,db angle){
    db co=cos(angle),si=sin(angle);
    return point(p.x*co-p.y*si,p.y*co+p.x*si);
}
int n,sz=0,top=0;
db a,b,r;
int main(){
    std::cin>>n>>b>>a>>r;
    db A=a/2-r,B=b/2-r;
    for(int i=1;i<=n;++i){
        db x,y,theta;
        std::cin>>x>>y>>theta;
        point center=point(x,y);
        point p1=point(A,B),p2=point(A,-B),
              p3=point(-A,B),p4=point(-A,-B);
        p[++sz]=rotate(p1,theta)+center,p[++sz]=rotate(p2,theta)+center,
        p[++sz]=rotate(p3,theta)+center,p[++sz]=rotate(p4,theta)+center;
    }
    for(int i=2;i<=sz;++i){
        if(p[i].y<p[1].y) std::swap(p[1],p[i]);
    }
    std::sort(p+2,p+sz+1,cmp);
    sta[++top]=p[1];
    for(int i=2;i<=sz;++i){
        while(top>1&&cross(sta[top],sta[top-1],p[i])>=0) --top;
        sta[++top]=p[i];
    } sta[top+1]=p[1];
//  for(int i=1;i<=top+1;++i) printf("%.5lf %.5lf\n",sta[i].x,sta[i].y);
    db ans=0;
    for(int i=1;i<=top;++i) ans+=dist(sta[i],sta[i+1]);
    printf("%.2lf\n",ans+2*pi*r);
    return 0;
}