P3829 题解

题目传送门

二维凸包模板传送门

题目分析

类似于凸包模板的一道题。

我们循序渐进地考虑，当半径 \(r=0\) 时，显然是一个二位凸包模板。

接着我们将圆弧加进去，仔细观察发现，我们构造出的凸包中的直线部分就是将圆心之间连起来的长度，而一个圆的贡献就是 \(\dfrac{1}{4}\) 个圆弧，四个圆贡献加起来正好就是一个圆的周长。

然后将模板改一下就做完了。

贴上代码

#include<bits/stdc++.h>
#define int long long
#define ok puts("Yes")
#define no puts("-1")
#define pi acos(-1)
#define at atan(A/B)
using namespace std;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-48;
		c=getchar();
	}
	return x*f;
}
const int maxn=2e5+5;
const double eps=1e-18;
double equ(double x){
	if(fabs(x)<eps) return 0;
	if(x>=0) return 1;
	else return -1;
}
int n;
int cnt;
double a,b,r,x,y,op;
double A,B,C;
double ans;
struct point{
	double x,y;
	point(double _x=0,double _y=0):x(_x),y(_y){}
	point operator + (const point &pt){return point(x+pt.x,y+pt.y);}
	point operator - (const point &pt){return point(x-pt.x,y-pt.y);}
}p[maxn];
bool cmp(point p,point q){
	if(equ(p.x-q.x)==0) return p.y<q.y;
	else return p.x<q.x;
}
struct my_stack{
	point stk[maxn];int sz=0;
    void push(point x){stk[sz++]=x;}
    point top(){return stk[sz-1];}
    point sec_top(){return stk[sz-2];}
    int size(){return sz;}
    void pop(){sz--;}
}st;
// bool slope(int aa,int b,int c){return (p[aa].y-p[b].y)*(p[b].x-p[c].x)>(p[aa].x-p[b].x)*(p[b].y-p[c].y);}
double dis(point a,point b){return sqrt((a.y-b.y)*(a.y - b.y)+(a.x-b.x)*(a.x-b.x));}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double len(point a){return sqrt(dot(a,a));}
double angle(point a,point b){return acos(dot(a,b)/len(a)/len(b));}
inline void init(){
	n=read();
	scanf("%lf%lf%lf",&a,&b,&r);
	A=a-2.0*r;B=b-2.0*r;C=sqrt(A*A+B*B)/2.0;
	for(register int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&x,&y,&op);
		double xx=cos(op+at)*C,yy=sin(op+at)*C;
		p[++cnt].x=x+xx;p[cnt].y=y+yy;
		p[++cnt].x=x-xx;p[cnt].y=y-yy;
		xx=cos(op-at)*C,yy=sin(op-at)*C;
		p[++cnt].x=x+xx;p[cnt].y=y+yy;
		p[++cnt].x=x-xx;p[cnt].y=y-yy;
	}
	sort(p+1,p+cnt+1,cmp);
}
signed main(){
	init();
	for(register int i=1;i<=cnt;++i){
		while(equ(cross(st.top()-st.sec_top(),p[i]-st.sec_top()))==-1&&st.size()>1) st.pop();
		st.push(p[i]);
	}
	int siz=st.size();
	for(register int i=cnt-1;i>=1;--i){
		while(equ(cross(st.top()-st.sec_top(),p[i]-st.sec_top()))==-1&&st.size()>siz) st.pop();
		st.push(p[i]);
	}
	for(register int i=0;i<st.size()-1;++i) ans+=dis(st.stk[i],st.stk[i+1]);
	ans+=2.0*pi*r;
	printf("%.2lf",ans);
}