萌新刚学OI1s,凸包板子玄关求调
查看原帖
萌新刚学OI1s,凸包板子玄关求调
613794
jianhe楼主2025/1/21 19:04

大概是样例二、三都过不去,样例二输出 41.3141.31,样例三输出 41.3541.35。(个人感觉可能是精度问题)

WA 20pts

调了一下午没调出来,qwq

/*
 * @Author: jianhe
 * @Date: 2025-01-21 11:31:52
 * @LastEditTime: 2025-01-21 18:53:12
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
const ll N=2e5+10,pi=acos(-1);
const db eps=1e-10;
ll n,top,ct;db ans,A,B,r,x,y,t;
struct P{
    db x,y;
    bool operator<(const P& B)const{return fabs(x-B.x)>=eps?B.x-x>=eps:B.y-y>=eps;}
    // ↑先按横坐标从小到大排,再按纵坐标从小到大排
    bool operator==(const P& B)const{return fabs(x-B.x)<eps&&fabs(y-B.y)<eps;}
    // 判相等
}a[N],s[N];
db K(P L,P R){return fabs(L.x-R.x)>=eps?(L.y-R.y)/(L.x-R.x):1e9;}
// 求斜率
db dis(P L,P R){return sqrtl((L.x-R.x)*(L.x-R.x)+(L.y-R.y)*(L.y-R.y));}
// 求距离
void solve(){// 凸包板子(复制的)
    top=0;
    for(int i=1;i<=n;i++){
        s[++top]=a[i];
        while(top>2&&K(s[top-2],s[top])<K(s[top-2],s[top-1])) s[top-1]=s[top],top--;
    }
    for(int i=1;i<top;i++) ans+=dis(s[i],s[i+1]);
}
void tubao(){
	sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;// 去重
    solve();
    reverse(a+1,a+n+1);solve();// 上下凸壳各求一遍
}
P calc(db x1,db y1){// 转化为 4 个点(应该是对的)
    db tt=t+atan2(y1-y,x1-x);
    return {x+cos(tt)*dis({x1,y1},{x,y}),y+sin(tt)*dis({x1,y1},{x,y})};
}
void mk(){a[++ct]=calc(x+B,y+A),a[++ct]=calc(x+B,y-A),a[++ct]=calc(x-B,y+A),a[++ct]=calc(x-B,y-A);}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>r;A=A/2-r,B=B/2-r;
    for(int i=1;i<=n;i++) cin>>x>>y>>t,mk();
    n<<=2;tubao();
    printf("%.2Lf",ans+2*pi*r+eps);// 加上圆的周长
    return 0;
}
2025/1/21 19:04
加载中...