bzoj 2829: 信用卡凸包 （凸包）

Description

Input

Output

Sample Input

Sample Output

HINT

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

Source

题解：凸包

以圆心为点做凸包，然后求凸包的周长，最后加上一个圆的周长。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100003using namespace std;int n,m;double a,b,r,pi=acos(-1.0);struct vector{	double x,y;	vector(double X=0,double Y=0) {		x=X,y=Y;	}}p[N],ch[N];bool Operator <(vector a,vector b){	return a.x<b.x||a.x==b.x&&a.y<b.y;}vector operator +(vector a,vector b){	return vector (a.x+b.x,a.y+b.y);}vector operator -(vector a,vector b){	return vector (a.x-b.x,a.y-b.y);}vector operator *(vector a,double k){	return vector (a.x*k,a.y*k);}vector rotate(vector a,double rad){	return vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}double cross(vector a,vector b){	return a.x*b.y-a.y*b.x;}double get_len(vector a){	return sqrt(a.x*a.x+a.y*a.y);}void convexhull(){	sort(p+1,p+n+1);	m=0;	for (int i=1;i<=n;i++) {		while (m>1&&cross(ch[m]-ch[m-1],p[i]-ch[m])<0) m--;		ch[++m]=p[i];	}	int k=m;	for (int i=n;i>=1;i--) {		while (m>k&&cross(ch[m]-ch[m-1],p[i]-ch[m])<0) m--;		ch[++m]=p[i];	}	m--;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d",&n);	scanf("%lf%lf%lf",&a,&b,&r);	int cnt=0;	for (int i=1;i<=n;i++) {		double x,y,rad;		scanf("%lf%lf%lf",&x,&y,&rad); 		double l=a-2.0*r; l/=2.0;		double d=b-2.0*r; d/=2.0; vector v; 		p[0]=vector(x,y);		p[++cnt].x=x+d; p[cnt].y=y+l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v; 		p[++cnt].x=x-d; p[cnt].y=y-l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;		p[++cnt].x=x+d; p[cnt].y=y-l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;		p[++cnt].x=x-d; p[cnt].y=y+l; v=rotate(p[cnt]-p[0],rad); p[cnt]=p[0]+v;	//	for (int j=cnt;j>=cnt-4+1;j--)	//	 cout<<p[j].x<<" "<<p[j].y<<endl;	}	n=cnt;	convexhull();	double ans=0;	for (int i=1;i<=m;i++) ans+=get_len(ch[i]-ch[i+1]);	ans+=pi*r*2.0;	PRintf("%.2lf/n",ans);}