萌新刚学OI1e-6s求助
查看原帖
萌新刚学OI1e-6s求助
367359
Neil_Qian楼主2024/1/13 22:47

Subtask1的第一个(但是编号是#2)死活过不去,是不是被卡精度了,求救QAQ

#include<bits/stdc++.h>
using namespace std;const double eps=1e-8;const int N=5e4+2;
struct Vector{
	double x,y,ang,Len;
	inline void update(){
		if(fabs(x)<eps)x=0;
		if(fabs(y)<eps)y=0;
	}
	inline double K(){return y/x;}
	Vector operator +(const Vector b){return Vector{x+b.x,y+b.y};}
	Vector operator -(const Vector b){return Vector{x-b.x,y-b.y};}
	bool operator <(const Vector b){
		return (fabs(ang-b.ang)<eps?Len<b.Len:ang<b.ang);
	}
}p[N],p1,p2,p3,p4,q1,q2,q3,q4,O;int n,s[N],tp;double Ox,Oy,t1,t2,t3,ans=1e10,k1,k2,b1,b2,b3,b4;
inline double dist(const Vector a,const Vector b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dot(const Vector a,const Vector b){return a.x*b.x+a.y*b.y;}
inline double cross(const Vector a,const Vector b){return a.x*b.y-a.y*b.x;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&p[i].x,&p[i].y);
		if(p[i].y<p[1].y||(fabs(p[i].y-p[1].y)<eps&&p[i].x<p[1].x))swap(p[1],p[i]);
	}
	O=p[1],Ox=p[1].x,Oy=p[1].y;
	for(int i=1;i<=n;i++)p[i].x-=Ox,p[i].y-=Oy,
		p[i].ang=atan2(p[i].y,p[i].x),p[i].Len=dist(p[i],Vector{0,0});
	sort(p+1,p+n+1),s[++tp]=1;
	for(int i=2;i<=n;i++){
		while(tp>=3&&cross(p[s[tp]]-p[s[tp-1]],p[i]-p[s[tp]])<eps)tp--;
		s[++tp]=i;
	}
	s[tp+1]=1;
	for(int i=1,j=3,l=2,r=2;i<=tp;i++){
		while(fabs(cross(p[s[i]]-p[s[i+1]],p[s[i]]-p[s[j]]))<
			fabs(cross(p[s[i]]-p[s[i+1]],p[s[i]]-p[s[j%tp+1]])))(j%=tp)++;
		r=max(r,j);
		while(l!=j&&dot(p[s[i+1]]-p[s[i]],p[s[l+1]]-p[s[l]])>-eps)(l%=tp)++;
		while(r!=i&&dot(p[s[i+1]]-p[s[i]],p[s[r+1]]-p[s[r]])<eps)(r%=tp)++;
		t1=abs(cross(p[s[i+1]]-p[s[i]],p[s[j]]-p[s[i+1]])),
		t2=dot(p[s[i+1]]-p[s[i]],p[s[l]]-p[s[i+1]])+
		dot(p[s[i+1]]-p[s[i]],p[s[i+1]]-p[s[r]]),
		t3=dot(p[s[i+1]]-p[s[i]],p[s[i+1]]-p[s[i]]);
		if(t1*t2/t3<ans){
			ans=t1*t2/t3;
			if(abs((p[s[i+1]]-p[s[i]]).x)<eps||abs((p[s[i+1]]-p[s[i]]).y)<eps){
				if(abs((p[s[i+1]]-p[s[i]]).x)<eps)
					p1=Vector{p[s[i]].x,p[r].y},p2=Vector{p[j].x,p[r].y},
					p3=Vector{p[j].x,p[l].y},p4=Vector{p[s[i]].x,p[l].y};
				else
					p1=Vector{p[r].x,p[s[i]].y},p2=Vector{p[r].x,p[j].y},
					p3=Vector{p[l].x,p[j].y},p4=Vector{p[l].x,p[s[i]].y};
			}
			else{
				k1=(p[s[i+1]]-p[s[i]]).K(),b1=p[s[i]].y-p[s[i]].x*k1,
				b2=p[s[j]].y-p[s[j]].x*k1,k2=-1/k1,b3=p[s[r]].y-p[s[r]].x*k2,
				b4=p[s[l]].y-p[s[l]].x*k2,p1=Vector{(b3-b1)/(k1-k2),(b3-b1)/(k1-k2)*k1+b1},
				p2=Vector{(b3-b2)/(k1-k2),(b3-b2)/(k1-k2)*k1+b2},
				p3=Vector{(b4-b2)/(k1-k2),(b4-b2)/(k1-k2)*k1+b2},
				p4=Vector{(b4-b1)/(k1-k2),(b4-b1)/(k1-k2)*k1+b1};
			}
		}
	}
	p1=p1+O,p2=p2+O,p3=p3+O,p4=p4+O,p1.update(),p2.update(),p3.update(),p4.update();
	return printf("%.5f\n%.5f %.5f\n%.5f %.5f\n%.5f %.5f\n%.5f %.5f\n",
	ans+eps,p4.x,p4.y,p3.x,p3.y,p2.x,p2.y,p1.x,p1.y),0;
}
2024/1/13 22:47
加载中...