调了好久了,真调不出来了
#include<bits/stdc++.h>
#include<numbers>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define eps 1e-12
using namespace std;
const int N=1e6+20;
struct node{
double x,y;
}p[N],stk[N];
int n;
double a,b,l;
double check(node a1,node a2,node b1,node b2){
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dist(node a,node b){
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
bool cmp(node p1,node p2){
double tmp=check(p[1],p1,p[1],p2);
if(tmp>0){
return 1;
}
if(tmp==0&&dist(p[1],p1)<dist(p[1],p2)){
return 1;
}
return 0;
}
void graham(){
sort(p+2,p+n+1,cmp);
// cout<<p[1].x<<" "<<p[1].y<<'\n';
stk[1]=p[1];
int cnt=1;
for(int i=2;i<=n;i++){
while(cnt>1&&check(stk[cnt-1],stk[cnt],stk[cnt],p[i])<=0){
cnt--;
}
cnt++;
stk[cnt]=p[i];
}
stk[cnt+1]=p[1];
double ans=0;
// puts("");
for(int i=1;i<=cnt;i++){
// cout<<stk[i].x<<" "<<stk[i].y<<'\n';
ans+=dist(stk[i],stk[i+1]);
}
// cout<<stk[cnt+1].x<<" "<<stk[cnt+1].y<<'\n';
printf("%.2lf",ans+numbers::pi*l*2);
}
node operator + (node a,node b){
return (node){a.x+b.x,a.y+b.y};
}
node operator - (node a,node b){
return (node){a.x-b.x, a.y-b.y};
}
node operator - (node a){
return (node){-a.x,-a.y};
}
node operator * (node a,double b){
return (node){a.x*b, a.y*b};
}
// bool operator < (const node& a, const node& b){
// return a.x==b.x?a.y<b.y:a.x<b.x;
// }
double ds;
void click(int k){
ds=p[1].y;
p[1].y=p[k].y;
p[k].y=ds;
ds=p[1].x;
p[1].x=p[k].x;
p[k].x=ds;
}
node ro(node a, double t) {
double c=cos(t),s=sin(t);
return (node){a.x*c-a.y*s, a.x*s+a.y*c};
}
int main(){
bool flagx=1,flagy=1;
cin>>n;
cin>>b>>a>>l;
a/=2.0;
b/=2.0;
for(int i=1;i<=n;i++){
int kf=(i-1)*4+1;
double x,y,t;
cin>>x>>y>>t;
x+=eps,y+=eps,t+=eps;
node cit=(node){x,y};
p[kf]=ro((node){a-l,b-l},t)+cit;
p[kf+1]=ro((node){l-a,b-l},t)+cit;
p[kf+2]=ro((node){l-a,l-b},t)+cit;
p[kf+3]=ro((node){a-l,l-b},t)+cit;
// cin>>p[i].x>>p[i].y;
// if(i!=1&&p[i].x!=p[i-1].x){
// flagx=0;
// }
// if(i!=1&&p[i].y!=p[i-1].y){
// flagy=0;
// }
// if(i!=1&&(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x))){
// click(i);
// }
}
// if(flagx){
// double minn=0.0,maxn=0.0;
// for(int i=1;i<=n;i++){
// minn=min(minn,p[i].y);
// maxn=max(maxn,p[i].y);
// }
// printf("%.2lf\n",2*(maxn-minn));
// return 0;
// }
// if(flagy){
// double minn=0.0,maxn=0.0;
// for(int i=1;i<=n;i++){
// minn=min(minn,p[i].x);
// maxn=max(maxn,p[i].x);
// }
// printf("%.2lf\n",2*(maxn-minn));
// return 0;
// }
n*=4;
graham();
}