P3829 [SHOI2012]信用卡凸包 题解

· · 题解

题面

题意解释

应该没有人像我一样做了 20 分钟才发现所有长方形大小一样吧。。。

分析

我们首先把样例的图画出来（大家都会，我就偷懒了）。不难发现对答案有贡献的是圆弧和作为长方形边的线段。根据范围的提示，我们先考虑 r=0 也就是长方形的情况。显然把所有顶点加入其中求凸包即为答案。不会的话左转模板区二维凸包。接下来，考虑加入圆弧的答案，观察其与加入圆弧之前的图形的关联，我们发现，其中的直线部分恰好等于圆心之间的连线。原因：\frac{1}{4} 的圆弧对应圆心角为直角，那么圆弧之间的这个四边形为长方形。那么我们在图中加入所有圆心，跑凸包算法即可。圆弧的贡献正好是一个整圆的周长，因为任意凸多边形外角和为 360^\circ。到这里我们惊喜地发现已经做完了！

复杂度：O(n\log n)，瓶颈在求凸包排序。

代码：

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a));
#define pc putchar
#define fast_iostream ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef double db;
const ld EPS=1e-8;
const ll INF=ll(1e9+7);
const ll LLINF=ll(1e18+7);
const ld LDEPS=1e-18;
const ld PI=3.14159265358979323846;
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline ld dmax(ld x,ld y){return x>y?x:y;}
inline ld dmin(ld x,ld y){return x<y?x:y;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
inline ll lowbit(ll x){return x&(-x);}
inline ll read(){ll read_result=0,is_below_0=0;char now_ch=0;while(!isdigit(now_ch)){is_below_0|=now_ch=='-';now_ch=getchar();}while(isdigit(now_ch)){read_result=(read_result<<3)+(read_result<<1)+(now_ch^48);now_ch=getchar();}return is_below_0?-read_result:read_result;}
inline ld dread(){ld x=0,d=0.1;char f=0,ch=getchar();while(!isdigit(ch))f|=(ch=='-'),ch=getchar();while(isdigit(ch)) x=x*10+ch-48,ch=getchar();if(ch=='.'){ch=getchar();while(isdigit(ch))x+=d*(ch^48),d*=0.1,ch=getchar();}return f?-x:x;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');}
const ll MAXN=2e5+7;
ll n,m;
db A,B,C,R;
short sgn(db x)
{
    if(fabs(x)<LDEPS)return 0;
    return x<0?-1:1;
}
struct Point
{
    db x,y;
    Point(){}
    Point(db _x,db _y):x(_x),y(_y){}
    bool operator<(const Point& xx)
    {
        if(sgn(x-xx.x)==0)return y<xx.y;
        return x<xx.x;
    }
    Point operator-(const Point& xx){return Point(x-xx.x,y-xx.y);}
    Point operator+(const Point& xx){return Point(x+xx.x,y+xx.y);}
    Point operator*(const ll& k){return Point(x*k,y*k);}
    Point operator/(const ll& k){return Point(x/k,y/k);}
}a[MAXN];
#define P Point
db Cross(P xx,P yy){return xx.x*yy.y-xx.y*yy.x;}
db Dot(P xx,P yy){return xx.x*yy.x+xx.y*yy.y;}
db Len(P xx){return sqrt(Dot(xx,xx));}
db Angle(P xx,P yy){return acos(Dot(xx,yy)/Len(xx)/Len(yy));}
db dis(P xx,P yy){return sqrt((xx.x-yy.x)*(xx.x-yy.x)+(xx.y-yy.y)*(xx.y-yy.y));}
struct Monostack{
    Point sta[MAXN];ll tp=0;
    void clear(){tp=0;}
    Point top(){return sta[tp-1];}
    Point top_2(){return sta[tp-2];}
    void push(Point x){sta[tp++]=x;}
    void pop(){tp--;}
    ll size(){return tp;}
}st;
db Andrew()
{
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++)
    {
        while(st.size()>1&&sgn(Cross(st.top()-st.top_2(),a[i]-st.top_2()))==-1)
            st.pop();
        st.push(a[i]);
    }
    ll lxy=st.size();
    for(ll i=n-1;i>=1;i--)
    {
        while(st.size()>lxy&&sgn(Cross(st.top()-st.top_2(),a[i]-st.top_2()))==-1)
            st.pop();
        st.push(a[i]);
    }
    db ans=0;
    for(ll i=0;i<st.size()-1;i++)
        ans+=dis(st.sta[i],st.sta[i+1]);
    return ans;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    m=read();A=dread(),B=dread(),R=dread();
    A-=2.0*R,B-=2.0*R;
    C=sqrt(A*A+B*B)/2.0;
    db al=atan(A/B);
    for(ll i=1;i<=m;i++)
    {
        db x=dread(),y=dread(),ang=dread();
        db dx=cos(ang+al)*C,dy=sin(ang+al)*C;
        a[++n]=P(x+dx,y+dy);
        a[++n]=P(x-dx,y-dy);
        dx=cos(ang-al)*C,dy=sin(ang-al)*C;
        a[++n]=P(x+dx,y+dy);
        a[++n]=P(x-dx,y-dy);
    }
    printf("%.2lf",(Andrew()+2.0*PI*R));
    return 0;
}