求助,在输入过程中貌似出了问题
查看原帖
求助,在输入过程中貌似出了问题
766764
shiruoyu114514楼主2023/7/20 20:37

当我尝试输出每次将要加入点集的四个点时,发现在样例二的第一张卡时,左上角的顶点为0.894427 2.68328 。

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>

using namespace std;

struct node{
    double x;
    double y;
};

int n;
vector<node> point;
vector<node> work;

double a,b,r;

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((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));
}

bool cmp(node a,node b){
    double tmp=check(point[1],a,point[1],b);
    if(tmp>0) 
        return 1;
    if(tmp==0&&dist(point[1],a)<dist(point[1],b)){
		return 1;
	}
    return 0;
}

void input(){
	node k;
	k.x=k.y=0;
	point.push_back(k);
	int _n;
	cin>>_n;
	double a,b,r;
	cin>>a>>b>>r;
	for(int i=1;i<=_n;i++){
		double x,y,sita;
		cin>>x>>y>>sita;
		node base[5];
		base[1].x=x-b/2+r;base[1].y=y+a/2-r;
		base[2].x=x-b/2+r;base[2].y=y-a/2+r;
		base[3].x=x+b/2-r;base[3].y=y+a/2-r;
		base[4].x=x+b/2-r;base[4].y=y-a/2+r;
		//for(int j=1;j<=4;j++){
		//	cout<<base[j].x<<" "<<base[j].y<<"\n";
		//}
		node newadd[5];
		for(int j=1;j<=4;j++){
			double sit=atan2(base[j].y,base[j].x);
		//	cout<<"sit:"<<sit<<"\n";
			double R=sqrt(pow(b-2*r,2)/4+pow(a-2*r,2)/4);
			sit+=sita;
		//	cout<<"sit after sita:"<<sit<<"\n";
			newadd[j].x=R*cos(sit);
			newadd[j].y=R*sin(sit);
		//	cout<<newadd[j].x<<" "<<newadd[j].y<<"\n";
			point.push_back(newadd[j]);
		}
	}
	n=4*_n;
}

double Do(){
    for(int i=1;i<=n;i++){
        if(i!=1){
        	if(point[i].y<point[1].y){
        	    swap(point[1],point[i]);
        	}
        	else if(point[i].y==point[1].y){
        		if(point[i].x<point[1].x){
        			swap(point[1],point[i]);
				}
			}
    	}
    }
    sort(point.begin()+2,point.end(),cmp);
    //for(int i=1;i<=n;i++){
    //	cout<<point[i].x<<" "<<point[i].y<<"\n";
	//} 
	work.push_back(point[1]);
    for(int i=2;i<=n;i++){
        while(work.size()>=2&&check(work[work.size()-2],work[work.size()-1],work[work.size()-1],point[i])<=0)
	        work.pop_back();
        work.push_back(point[i]);
        /*for(int j=0;j<work.size();j++){
        	cout<<work[j].x<<" "<<work[j].y<<"\n";
		}
		cout<<"\n";
		*/
    }
    work.push_back(point[1]);
	/*for(int j=0;j<work.size();j++){
        cout<<work[j].x<<" "<<work[j].y<<"\n";
	}*/
	double ans=0;
    for(int i=0;i<work.size()-1;i++){
	    ans+=dist(work[i],work[i+1]);
    }
    return ans;
}

int main(){
	input();
	printf("%.2lf",Do()+2*acos(-1)*r);
}
2023/7/20 20:37
加载中...