Bzoj2829 信用卡凸包

凸包模板题+1

Posted by yjjr's blog on January 19, 2018

标签:凸包

题目

题目传送门

Description

这里写图片描述 Input 这里写图片描述 Output 这里写图片描述 Sample Input 2

6.0 2.0 0.0

0.0 0.0 0.0

2.0 -2.0 1.5707963268

Sample Output 21.66

HINT

本样例中的2张信用卡的轮廓在上图中用实线标出,如果视1.5707963268为

Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)

#分析

凸包加一个圆的周长,注意建图

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define pi acos(-1)
#define eps 1e-8
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=4e5+6;
double ans,a,b,r;int n,cnt=0,top;
struct P{
	double x,y;
	P(double xx=0,double yy=0){x=xx,y=yy;}
	friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
	friend double operator * (P a,P b){return a.x*b.y-a.y*b.x;}
	friend bool operator < (P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y;}
	friend double dis2(P a){return (double)((double)a.x*a.x+(double)a.y*a.y);}
}p[maxn],s[maxn];
struct node{double x,y,angle;}w[maxn];
inline P move(P a,double d,double Angle){return P(a.x+d*cos(Angle),a.y+d*sin(Angle));}
inline bool cmp(P a,P b){return fabs((a-p[1])*(b-p[1]))<eps?dis2(p[1]-a)<dis2(p[1]-b):(a-p[1])*(b-p[1])>0;}
void graham(){
	rep(i,1,cnt)if(p[i]<p[1])swap(p[i],p[1]);
	sort(p+2,p+cnt+1,cmp);
	rep(i,1,cnt){
		while(top>1&&(s[top]-s[top-1])*(p[i]-s[top-1])<-eps)top--;
		s[++top]=p[i];
	}
	s[top+1]=s[1];
	rep(i,1,top)ans+=sqrt(dis2(s[i]-s[i+1]));
}
int main(){
	n=read();
	cin>>a>>b>>r;a-=2*r,b-=2*r;
	ans+=2*pi*r;
	rep(i,1,n)cin>>w[i].x>>w[i].y>>w[i].angle;
	rep(i,1,n)
		rep(j,0,3){
			P t=move(P(w[i].x,w[i].y),b/2,w[i].angle+j*pi/2);
			p[++cnt]=move(t,a/2,w[i].angle+(j+1)*pi/2);
			swap(a,b);
		}
	graham();
	printf("%.2lf\n",ans);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr