请不要加强数据(bushi
查看原帖
请不要加强数据(bushi
684245
zhangyaiwei楼主2024/8/16 11:55
#include<bits/stdc++.h>
using namespace std;
double a,b,x,y,c,r,ans;
int n;
struct Pt{
	double x,y;
}Pts[41111];
bool cmp(Pt a,Pt b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool C[41111];
stack<int> tb;
bool ONL(int o,int a,int b){
	return (Pts[a].x-Pts[o].x)*(Pts[b].y-Pts[o].y)-(Pts[a].y-Pts[o].y)*(Pts[b].x-Pts[o].x)>=0;
}
int main(){
	cin>>n>>a>>b>>r;
	double X=b/2-r,Y=a/2-r;
	for(int i=1;i<=n;i++){
		int W=(i-1)*4;
		cin>>x>>y>>c;
		Pts[W+1].x=X*cos(c)-Y*sin(c)+x,Pts[W+1].y=X*sin(c)+Y*cos(c)+y;
		Pts[W+2].x=-X*cos(c)-Y*sin(c)+x,Pts[W+2].y=-X*sin(c)+Y*cos(c)+y;
		Pts[W+3].x=X*cos(c)+Y*sin(c)+x,Pts[W+3].y=X*sin(c)-Y*cos(c)+y;
		Pts[W+4].x=-X*cos(c)+Y*sin(c)+x,Pts[W+4].y=-X*sin(c)-Y*cos(c)+y;
	}
	sort(Pts+1,Pts+1+n*4,cmp);
	tb.push(1);
	tb.push(2);
	C[2]=1;
	for(int i=3;i<=n*4;i++){
		while(tb.size()>1){
			int A=tb.top();
			tb.pop();
			int O=tb.top();
			C[A]=0;
			if(ONL(O,A,i)){
				tb.push(A);
				C[A]=1;
				break;
			}
		}
		tb.push(i);
		C[i]=1;
	}
	for(int i=n*4;i;i--){
		if(C[i]) continue;
		while(tb.size()>1){
			int A=tb.top();
			tb.pop();
			int O=tb.top();
			C[A]=0;
			if(ONL(O,A,i)){
				tb.push(A);
				C[A]=1;
				break;
			}
		}
		tb.push(i);
		C[i]=1;
	}
	while(tb.size()>1){
		int A=tb.top();
		tb.pop();
		int B=tb.top();
		ans+=sqrt((Pts[A].x-Pts[B].x)*(Pts[A].x-Pts[B].x)+(Pts[A].y-Pts[B].y)*(Pts[A].y-Pts[B].y));
	}
	printf("%.2f",ans+2*r*acos(-1));
}

第二个测试点输出 49.60,但是AC了

不建议加强数据,不然我就AC不了了

2024/8/16 11:55
加载中...