70分求调
查看原帖
70分求调
542567
CyberPrisoner楼主2023/7/28 19:41
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int n,top,use[N],cnt;
double ans,l;
int st[N];
double a,b;
struct vec{
	double x,y;
	bool operator <(const vec&rhs)const{
		return x!=rhs.x? x<rhs.x:y<rhs.y;
	}
	vec operator -(const vec&rhs)const{
		return (vec){x-rhs.x,y-rhs.y};
	}
	vec operator +(const vec&rhs)const{
		return (vec){x+rhs.x,y+rhs.y};
	}
	double operator *(const vec&rhs)const{
		return x*rhs.y-y*rhs.x;
	}
}p[N];
void solve(double x,double y,double deg){
	//double len=sqrt(a*a+b*b)/2;
	vec mid=(vec){x,y};
	vec left=(vec){x+a*cos(deg),y+a*sin(deg)};
	vec right=(vec){x-a*cos(deg),y-a*sin(deg)};
	vec up=(vec){x-b*sin(deg),y+b*cos(deg)};
	vec below=(vec){x+b*sin(deg),y-b*cos(deg)};
	p[++cnt]=left+up;p[cnt]=p[cnt]-mid;
	p[++cnt]=up+right;p[cnt]=p[cnt]-mid;
	p[++cnt]=right+below;p[cnt]=p[cnt]-mid;
	p[++cnt]=below+left;p[cnt]=p[cnt]-mid;
	
}
double dist(vec a,vec b){
	vec c=a-b;
	return sqrt(c.x*c.x+c.y*c.y);
}
void Andrew(){
	sort(p+1,p+cnt+1);
	st[++top]=1;
	for(int i=2;i<=cnt;i++){
		while(top>=2&&(p[st[top]]-p[st[top-1]])*(p[i]-p[st[top]])<=0)
			use[st[top--]]=0;
		use[i]=1;
		st[++top]=i;
	}
	int temp=top;
	for(int i=cnt-1;i>=1;i--){
		if(use[i])continue;
		while(top>temp&&(p[st[top]]-p[st[top-1]])*(p[i]-p[st[top]])<=0)
		use[st[top--]]=0;
		use[i]=1;
		st[++top]=i;
	}
}
int main(){
	cin>>n;
	cin>>a>>b>>l;
	a/=2,b/=2;
	a-=l,b-=l;
	for(int i=1;i<=n;i++){
		double x,y,deg;
		cin>>x>>y>>deg;
		solve(x,y,deg);
	}
	ans=2.0*l*acos(-1);
	Andrew();
	for(int i=2;i<=top;i++){
		ans+=dist(p[st[i]],p[st[i-1]]);
	}
	//cout<<fixed<<setprecision(5)<<ans*100<<" "<<(int)(ans*100)<<endl;
	//f(ans*100-(int)(ans*100)>=0.5)
	printf("%.2lf", ans);
	//else printf("%.2lf", ans);
	return 0;
}
2023/7/28 19:41
加载中...