[SHOI2012]信用卡凸包

题目

对于一个圆滑处理过的矩形，我们发现其周长就是四个(frac{1}{4})圆的圆心形成的矩形周长再加上一个圆的周长

于是我们大力猜想，答案就是把所有(frac{1}{4})圆的圆心拿下来建个凸包，凸包的周长再加上一个圆的周长即可；发现这样非常正确，感性理解一下大概是这个凸多边形转过了一个(2pi)，所以各圆弧的和就是一个完整的圆

于是现在就变成了一个板子题了，代码

#include<bits/stdc++.h>
#define re register
#define sqr(x) ((x)*(x))
#define double long double
#define cK ((p[i]-st[top-1])*(st[top]-st[top-1]))
const int maxn=5e4+5;
const double eps=1e-7;
const double pi=acos(-1);
int top,n,N;
struct pt{double x,y;}p[maxn],st[maxn];
inline int dcmp(double a,double b) {return a+eps>b&&a-eps<b;}
inline double operator*(const pt &A,const pt &B) {return A.x*B.y-A.y*B.x;}
inline pt operator+(const pt &A,const pt &B) {return (pt){A.x+B.x,A.y+B.y};}
inline pt operator-(const pt &A,const pt &B) {return (pt){A.x-B.x,A.y-B.y};}
inline double dis(const pt &A,const pt &B) {return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
inline double size(const pt &A) {return dis((pt){0,0},A);}
inline pt rotate(const pt &O,const pt &A,double det) {
	pt B;B=A-O;double c=cos(det),s=sin(det);
	return O+(pt){B.x*c-B.y*s,B.x*s+B.y*c};
}
inline int cmp(const pt &A,const pt &B) {
	double t=A*B;
	return dcmp(t,0)?size(A)<size(B):(t>0);
}
int main() {
	//freopen("data.in","r",stdin);
	double a,b,det;pt nw,o;double A,B,r;
	scanf("%d%Lf%Lf%Lf",&n,&B,&A,&r);A*=0.5,B*=0.5;
	for(re int i=1;i<=n;i++) {
		scanf("%Lf%Lf%Lf",&a,&b,&det);o.x=a,o.y=b;
		nw.x=a-A+r,nw.y=b+B-r;
		p[++N]=rotate(o,nw,det);
		nw.x=a+A-r,nw.y=b+B-r;
		p[++N]=rotate(o,nw,det);
		nw.x=a-A+r,nw.y=b-B+r;
		p[++N]=rotate(o,nw,det);
		nw.x=a+A-r,nw.y=b-B+r;
		p[++N]=rotate(o,nw,det);
	}
	//for(re int i=1;i<=N;i++) printf("%.4Lf %.4Lf
",p[i].x,p[i].y);puts("");
	pt S;S=p[1];
	for(re int i=2;i<=N;i++)
		if(p[i].x<S.x) S=p[i];else if(dcmp(p[i].x,S.x)&&p[i].y<S.y) S=p[i];
	for(re int i=1;i<=N;i++) p[i]=p[i]-S;
	std::sort(p+1,p+N+1,cmp);
	for(re int i=1;i<=N;++i) {
		while(top>1&&(cK>0||dcmp(cK,0))) --top;
		st[++top]=p[i];
	}
	st[top+1]=st[1];double ans=2.0*pi*r;
	for(re int i=1;i<=top;i++) ans+=dis(st[i],st[i+1]);
	printf("%.2Lf
",ans);return 0;
}
//g++ lg3829.cpp -o lg3829