60pts求条
查看原帖
60pts求条
676668
SkokraFX楼主2024/12/7 23:17

调了好久了,真调不出来了

#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();
} 
2024/12/7 23:17
加载中...