凸包模板求调qwq
查看原帖
凸包模板求调qwq
763878
Jerry_heng楼主2024/5/10 18:20
#include<bits/stdc++.h>
using namespace std;
int n,cnt=1;
double a,b,r,xx,yy,t,eps=1e-8;
struct node{
    double x,y;
}p[40000005],s[40000005],pp;
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 d(node p1,node p2){
    return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(node p1,node p2){
    double t=check(p[1],p1,p[1],p2);
    if(t>0)return 1;
    if(t==0&&d(p[1],p1)<d(p[1],p2)) return 1;
    return 0;
}
int main(){
	scanf("%d",&n);
	scanf("%lf%lf%lf",&a,&b,&r);
    for(int i=0;i<n;i++){
        scanf("%lf%lf%lf",&xx,&yy,&t);
        xx+=eps;
        yy+=eps;
        t+=eps;
        p[i*4+1].x=(b/2-r)*cos(t)-(a/2-r)*sin(t)+xx;
        p[i*4+1].y=(a/2-r)*cos(t)+(b/2-r)*sin(t)+yy;
        if(p[i*4+1].y<p[1].y)swap(p[i*4+1].y,p[1].y);
        p[i*4+2].x=-(b/2-r)*cos(t)-(a/2-r)*sin(t)+xx;
        p[i*4+2].y=(a/2-r)*cos(t)-(b/2-r)*sin(t)+yy;
        if(p[i*4+2].y<p[1].y)swap(p[i*4+2].y,p[1].y);
        p[i*4+3].y=-(a/2-r)*cos(t)+(b/2-r)*sin(t)+yy;
        p[i*4+3].x=(b/2-r)*cos(t)+(a/2-r)*sin(t)+xx;
        if(p[i*4+3].y<p[1].y)swap(p[i*4+3].y,p[1].y);
        p[i*4+4].x=-(b/2-r)*cos(t)+(a/2-r)*sin(t)+xx;
        p[i*4+4].y=-(a/2-r)*cos(t)-(b/2-r)*sin(t)+yy;
        if(p[i*4+4].y<p[1].y)swap(p[i*4+4].y,p[1].y);
    } 
    n*=4;
    sort(p+2,p+1+n,cmp);
    s[1]=p[1];
    for(int i=2;i<=n;i++){
        while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<0) 
			cnt--;
        cnt++;
        s[cnt]=p[i];
    }
    s[cnt+1]=p[1];
    double ans=0; 
    for(int i=1;i<=cnt;i++) 
		ans+=d(s[i],s[i+1]);
    printf("%.2lf\n",ans+3.1415926*2*r);
    return 0;
}
2024/5/10 18:20
加载中...