[FJWC2015]信用卡凸包

时间限制：1000MS

内存限制：131072KB

Description

信用卡是一个矩形，唯四个角作了圆滑处理，使它们都与矩形四边相切的1/4圆，如下图所示。现在平面上有一些规格相同的信用卡，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧（具体例子请看样例）。

Input Format

输入的第一行是一个正整数n，表示信用卡的张数。

第二行包含三个实数a, b,r，分别表示信用卡（圆滑处理前）竖直方向的长度、水平方向的长度，以及1/4圆的半径。

之后n行，每行包含三个实数x, y, θ，分别表示一张信用卡中心（即对角线交点）的横、纵坐标，以及绕中心逆时针旋转的弧度。

Output Format

输出只有一行，包含一个实数，表示凸包的周长，四舍五入精确到小数点后2位。

Sample Input & Output：略

Hint

【样例1 说明】 

本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为pi/2，则其凸包的周长为16+4sqrt(2)。

【样例2说明】 

本样例中的3张信用卡的轮廓在下图中用实线标出。

【样例3说明】

本样例中的3张信用卡的轮廓在下图中用实线标出。

 【数据规模】

对于100%的数据，有0.1 ≤ a, b≤ 1000000.0，以及0.0 ≤ r< min{a/4, b/4}，n≤100000

对所有的信用卡，有|x|, |y| ≤ 1000000.0，以及0 ≤ θ< 2π。

对于50%的数据，n≤2。:-)

对于70%的数据，n≤100。

其中两组数据r=0。

另外其中三组数据θ=0.

另外还有一组数据r=θ=0.

【题解】

我们发现，要直接求信用卡凸包比较复杂。

我们会发现，只需要求圆心的凸包即可，然后最后答案加上$2πr$就行了。

于是就直接做啦~

感谢97小叶子11和n+e的指导。

# include <stdio.h>
# include <algorithm>
# include <math.h>
# include <vector>
using namespace std;
int d[4][2] = {1, 1, 1, -1, -1, 1, -1, -1};
const double eps=1e-7,pi=acos(-1.0);
inline double abs(double a) {
	return a<0?-a:a;
}
inline double add(double a,double b) {
	if (abs(a+b)<eps*(abs(a)+abs(b)))return 0;
	return a+b;
}
struct P {
	double x,y;
	P () {}
	P (double x,double y):x(x),y(y){}
	P operator + (P a) {
		return P(add(x,a.x),add(y,a.y));
	}
	P operator - (P a) {
		return P(add(x,-a.x),add(y,-a.y));
	}
	P operator * (double d) {
		return P(x*d,y*d);
	}
	double dot(P a) {
		return add(x*a.x,y*a.y);
	}
	double det(P a) {
		return add(x*a.y,-y*a.x);
	}
};
P rotate(P a,double rot) {
	return P(a.x*cos(rot)-a.y*sin(rot),a.x*sin(rot)+a.y*cos(rot));
}
inline int cmp_x(P a, P b) {
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
inline vector<P> convexhull(vector<P>ps) {
	int n=ps.size(),k=0;
	sort(ps.begin(),ps.end(),cmp_x);
	vector<P> qs(n*2);
	for (int i=0;i<n;++i) {
		while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)--k;
		qs[k++]=ps[i];
	}
	for (int i=n-2,t=k;i>=0;--i) {
		while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)--k;
		qs[k++]=ps[i];
	}
	qs.resize(k-1);
	return qs;
} 
int N;double A,B,r,z,ans;
inline double dis(P a,P b) {
	return sqrt((a-b).dot(a-b));
}
int main() {
	vector<P>ps;
	scanf("%d",&N);
	scanf("%lf%lf%lf",&A,&B,&r);A=A/2-r,B=B/2-r;
	for(int i=1;i<=N;++i) {
		P b;
		scanf("%lf%lf%lf",&b.x,&b.y,&z);
		P t;
		for (int j=0;j<4;++j) {
			t=rotate(P(d[j][0]*B,d[j][1]*A),z)+b;
			ps.push_back(t);
		}
	}
	vector<P>qs=convexhull(ps);
	int s=qs.size();ans=0.0;
	for (int i=0;i<s-1;++i) 
		ans+=dis(qs[i],qs[i+1]);
	ans+=dis(qs[s-1],qs[0]);
	ans+=2*pi*r;
	printf("%.2lf\n",ans);
	return 0;
}