Luogu

分析

发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。

于是把每张信用卡的四个顶点拿出来,求一个凸包,再用这个凸包的周长加上 $2\pi r$ 就是答案了。

具体怎么求出四个顶点,可以先求出中心点,然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。

然后就做完了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=40000+10;

int n,tot,top;

struct Point { double x,y; } p[N],s[N];
typedef Point Vector;
Point operator +(Point a,Vector b) { return (Point){a.x+b.x,a.y+b.y}; }
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
inline Vector rotate(Vector a,double t) {
    double c=cos(t),s=sin(t);
    return (Vector){a.x*c-a.y*s,a.x*s+a.y*c};
}

inline double dis(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline int cmp(Point a,Point b) {
    Vector x=a-p[1],y=b-p[1];
    double A=atan2(x.y,x.x),B=atan2(y.y,y.x);
    if (A!=B) return A<B;
    else return a.x<b.x;
}

inline void Graham() {
    int pos=1;
    for (re int i=2;i<=tot;++i)
        if (p[i].x<p[pos].x||(p[i].x==p[pos].x&&p[i].y<p[pos].y)) pos=i;
    swap(p[pos],p[1]),sort(p+2,p+tot+1,cmp);
    s[top=1]=p[1];
    for (re int i=2;i<=tot;++i) {
        while (top>1&&cross(s[top]-s[top-1],p[i]-s[top])<=0) --top;
        s[++top]=p[i];
    }
    s[top+1]=s[1];
}

int main() {
    n=read();
    double a,b,r; scanf("%lf%lf%lf",&a,&b,&r); a-=2*r,b-=2*r;
    for (re int i=1;i<=n;++i) {
        double x,y,t; scanf("%lf%lf%lf",&x,&y,&t);
        Point o=(Point){x,y};
        p[++tot]=o+rotate((Vector){b/2,a/2},t);
        p[++tot]=o+rotate((Vector){b/2,-a/2},t);
        p[++tot]=o+rotate((Vector){-b/2,a/2},t);
        p[++tot]=o+rotate((Vector){-b/2,-a/2},t);
    }
    Graham(); double ans=2*acos(-1)*r;
    for (re int i=1;i<=top;++i) ans+=dis(s[i],s[i+1]);
    printf("%.2lf\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 01 PM