凸包 70 pts 求调
查看原帖
凸包 70 pts 求调
604906
Guizy楼主2024/7/12 19:36
#include<bits/stdc++.h>
using namespace std;

const int eps=1e-11;
const int Max=400005;
struct point{
	double x,y;
}p[Max],s[Max];
point operator+(point a,point b){
	return (point){a.x+b.x,a.y+b.y};
}
double ans,aa,bb,rr,tx,ty,theta;
int n,t,cnt;

double dist(point a,point b){
	//<0 turn right;>0 turn left
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double check(point a1,point a2,point b1,point b2){
	return (a2.x-a1.x)*(b2.y-b1.y)-(a2.y-a1.y)*(b2.x-b1.x);
}

bool cmp(point a,point b){
	double tmp=check(p[1],a,p[1],b);
	if(tmp>0)//turn left
		return 1;
	if(tmp==0&&dist(p[1],a)<dist(p[1],b))
		return 1;
	return 0;
}

point rotate(point a,double alpha){
	return {a.x*cos(alpha)-a.y*sin(alpha),a.y*cos(alpha)+a.x*sin(alpha)};
}

int main(){
	
	cin.tie(0)->sync_with_stdio(0);
	
	cin>>n>>aa>>bb>>rr;
	aa/=2,bb/=2;
	for(int i=1;i<=n;i++){
		cin>>tx>>ty>>theta;
		point tmp={tx+eps,ty+eps};
		p[++cnt]=rotate({aa-rr,bb-rr},theta)+tmp;
		p[++cnt]=rotate({rr-aa,rr-bb},theta)+tmp;
		p[++cnt]=rotate({aa-rr,rr-bb},theta)+tmp;
		p[++cnt]=rotate({rr-aa,bb-rr},theta)+tmp;
	}
	n<<=2;
	for(int i=1;i<=n;i++){
		if(i==1) continue;
		if(p[i].y<p[1].y) swap(p[1],p[i]);
		else if(p[i].y==p[1].y&&p[i].x<p[1].x) swap(p[1],p[i]);
	}
	sort(p+2,p+n+1,cmp);	
	
	s[++t]=p[1];
	for(int i=2;i<=n;i++){
		while(t>1&&check(s[t-1],s[t],s[t],p[i])<=0) t--;
		s[++t]=p[i];
	}	
	s[t+1]=p[1];
	for(int i=1;i<=t;i++)
		ans+=dist(s[i],s[i+1]);
	ans+=acos(-1.0)*2*rr;
	cout<<fixed<<setprecision(2)<<ans;
}
2024/7/12 19:36
加载中...