QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#445860#6763. Triangle PendantliuhengxiWA 0ms2148kbC++146.5kb2024-06-16 15:55:442024-06-16 15:55:45

Judging History

你现在查看的是最新测评结果

  • [2024-06-16 15:55:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:2148kb
  • [2024-06-16 15:55:44]
  • 提交

answer

// created:  Jun/15/2024 15:47:15
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr double eps=1e-13;
struct vec2
{
	double x,y;
	vec2(){}
	vec2(double x_,double y_):x(x_),y(y_){}
	vec2 operator-()const{return vec2(-x,-y);}
	friend vec2 operator+(const vec2 &a,const vec2 &b){return vec2(a.x+b.x,a.y+b.y);}
	friend vec2 operator-(const vec2 &a,const vec2 &b){return vec2(a.x-b.x,a.y-b.y);}
	friend vec2 operator*(double b,const vec2 &a){return vec2(a.x*b,a.y*b);}
	friend vec2 operator*(const vec2 &a,double b){return vec2(a.x*b,a.y*b);}
	friend vec2 operator/(const vec2 &a,double b){return vec2(a.x/b,a.y/b);}
	friend double operator*(const vec2 &a,const vec2 &b){return a.x*b.x+a.y*b.y;}
	double len2()const{return x*x+y*y;}
	double len()const{return hypot(x,y);}
	vec2 norm()const{return *this/len();}
	vec2 perp()const{return vec2(-y,x);}
};
struct vec3
{
	double x,y,z;
	vec3(){}
	vec3(double x_,double y_,double z_):x(x_),y(y_),z(z_){}
	friend vec3 operator+(const vec3 &a,const vec3 &b){return vec3(a.x+b.x,a.y+b.y,a.z+b.z);}
	friend vec3 operator-(const vec3 &a,const vec3 &b){return vec3(a.x-b.x,a.y-b.y,a.z-b.z);}
	friend vec3 operator*(double b,const vec3 &a){return vec3(a.x*b,a.y*b,a.z*b);}
	friend vec3 operator*(const vec3 &a,double b){return vec3(a.x*b,a.y*b,a.z*b);}
	friend vec3 operator/(const vec3 &a,double b){return vec3(a.x/b,a.y/b,a.z/b);}
	friend double operator*(const vec3 &a,const vec3 &b){return a.x*b.x+a.y*b.y+a.z*b.z;}
	friend vec3 operator^(const vec3 &a,const vec3 &b){return vec3(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
	double len2()const{return x*x+y*y+z*z;}
	double len()const{return sqrt(len2());}
	vec3 norm()const{return *this/len();}
};
#ifdef LOCAL
void print(vec3 a){printf("=(%lf,%lf,%lf)\n",a.x,a.y,a.z);}
#endif
struct line
{
	vec2 a,b;
	line()=delete;
};
struct circle
{
	vec2 a;double r;
	circle(vec2 a_,double r_):a(a_),r(r_){}
	friend pair<bool,pair<vec2,vec2>> operator&(const circle &u,const circle &v)
	{
		double d2=(u.a-v.a).len2(),ur=u.r*u.r,vr=v.r*v.r;
		double l=0.5*(vr-ur)/d2;
		vec2 mid=u.a*(0.5+l)+v.a*(0.5-l);
		double dt=0.25*(-1.0+(2.0*(ur+vr)-(ur-vr)*(ur-vr)/d2)/d2);
		if(dt<-eps)return {false,{vec2(),vec2()}};
		if(dt<eps)return {true,{mid,mid}};
		vec2 dv=sqrt(dt)*(v.a-u.a).perp();
		return {true,{mid+dv,mid-dv}};
	}
};
struct circle3d
{
	vec3 a,n;double r;
	circle3d(vec3 a_,vec3 n_,double r_):a(a_),n(n_),r(r_){}
	friend pair<bool,pair<vec3,vec3>> operator&(const circle3d &u,const circle3d &v)// coplanar
	{
		double d2=(u.a-v.a).len2(),ur=u.r*u.r,vr=v.r*v.r;
		double l=0.5*(vr-ur)/d2;
		vec3 mid=u.a*(0.5+l)+v.a*(0.5-l);
		double dt=0.25*(-1.0+(2.0*(ur+vr)-(ur-vr)*(ur-vr)/d2)/d2);
		if(dt<-eps)return {false,{vec3(),vec3()}};
		if(dt<eps)return {true,{mid,mid}};
		vec3 dv=sqrt(dt)*((v.a-u.a)^u.n);
		return {true,{mid+dv,mid-dv}};
	}
};
struct sphere
{
	vec3 a;double r;
	sphere(vec3 a_,double r_):a(a_),r(r_){}
	friend pair<bool,circle3d> operator&(const sphere &u,const sphere &v)
	{
		double d2=(u.a-v.a).len2(),ur=u.r*u.r,vr=v.r*v.r;
		double l=0.5*(vr-ur)/d2;
		vec3 mid=u.a*(0.5+l)+v.a*(0.5-l);
		double dt=0.25*(-1.0+(2.0*(ur+vr)-(ur-vr)*(ur-vr)/d2)/d2);
		if(dt<-eps)return {false,circle3d(vec3(),vec3(1,0,0),0)};
		if(dt<eps)return {true,circle3d(mid,(v.a-u.a).norm(),0)};
		return {true,circle3d(mid,(v.a-u.a).norm(),sqrt(dt)*(v.a-u.a).len())};
	}
	friend pair<bool,pair<vec3,vec3>> operator&(const circle3d &u,const sphere &v)
	{
		double d=u.n*(u.a-v.a);
		if(d*d/(v.r*v.r)-1>eps)return {false,{vec3(),vec3()}};
		return u&circle3d(v.a+d*u.n,u.n,sqrt(max(v.r*v.r-d*d,0.0)));
	}
};
bool h1(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc)
{                                                        
	vec2 a(0,0),b(ab,0);                                 
	vec2 c=(circle(a,ac)&circle(b,bc)).second.first;     
	vec2 o=(a+b+c)/3;
	vec2 g=(a-o).norm();
	vec2 d=a+g*la;
	if((d-b).len()>lb+eps)return false;
	if((d-c).len()>lc+eps)return false;
	ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
	return true;
}                                                        
bool h2(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc)
{                                                        
	vec2 a(0,0),b(ab,0);                                 
	vec2 c=(circle(a,ac)&circle(b,bc)).second.first;     
	vec2 o=(a+b+c)/3;
	vec2 d;
	{
		pair<bool,pair<vec2,vec2>> cd=circle(b,lb)&circle(c,lc);
		if(!cd.first)return false;
		vec2 ga=(c-b).perp();
		if((a-b)*ga<0)ga=-ga;
		if((cd.second.first-c)*ga<0)d=cd.second.first;
		else d=cd.second.second;
	}
	if((d-a).len()>la+eps)return false;
	vec2 g=(d-o).norm();
	ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
	return true;
}                                                        
bool h3(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc)
{
	vec3 a,b,c;
	{
		vec2 a2(0,0),b2(ab,0);                                 
		vec2 c2=(circle(a2,ac)&circle(b2,bc)).second.first;     
		a=vec3(a2.x,a2.y,0);
		b=vec3(b2.x,b2.y,0);
		c=vec3(c2.x,c2.y,0);
	}
	vec3 o=(a+b+c)/3;
	vec3 d=((sphere(a,la)&sphere(b,lb)).second&sphere(c,lc)).second.first;
	vec3 g=(d-o).norm();
	ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
	return true;
}
void solve()
{
	double la,lb,lc,bc,ca,ab;
	{
		int xx,yy,zz,aa,bb,cc;read(xx,yy,zz,aa,bb,cc);
		la=xx;lb=yy;lc=zz;bc=aa;ca=bb;ab=cc;
	}
	bool ok=false;
	double ansa,ansb,ansc;
	ok=ok||h1(la,lb,lc,bc,ca,ab,ansa,ansb,ansc);
	ok=ok||h1(lb,lc,la,ca,ab,bc,ansb,ansc,ansa);
	ok=ok||h1(lc,la,lb,ab,bc,ca,ansc,ansa,ansb);
	ok=ok||h2(la,lb,lc,bc,ca,ab,ansa,ansb,ansc);
	ok=ok||h2(lb,lc,la,ca,ab,bc,ansb,ansc,ansa);
	ok=ok||h2(lc,la,lb,ab,bc,ca,ansc,ansa,ansb);
	ok=ok||h3(la,lb,lc,bc,ca,ab,ansa,ansb,ansc);
	printf("%.9lf %.9lf %.9lf\n",ansa,ansb,ansc);
}
int main()
{
	int tt;
	read(tt);
	while(tt--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 2148kb

input:

2
1 1 1 1 1 1
2 3 3 1 1 1

output:

-0.816496581 -0.816496581 -0.816496581
-2.000000000 -2.866025404 -2.866025404

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 2092kb

input:

1000
21 2 14 12 13 4
29 19 13 15 10 17
29 24 15 29 24 23
29 17 30 18 9 25
27 24 30 16 4 15
28 13 17 12 21 16
16 22 10 22 15 8
15 23 24 23 27 13
26 3 27 15 16 17
5 8 20 17 6 12
24 14 13 15 19 13
27 22 18 18 23 30
22 18 14 11 29 28
7 13 22 22 17 11
19 9 16 22 20 17
21 14 20 6 29 25
20 10 19 9 27 27
17...

output:

-2.935856728 -2.000000000 -13.352349000
-22.146476218 -16.076204705 -12.241826659
-28.027431433 -18.318582636 -8.243362186
-27.266119651 -13.159319584 -26.882525398
-26.534933367 -22.066632133 -29.616079569
-26.967804477 -12.557669396 -14.186722135
-15.778595669 -20.862676912 -5.155856507
-10.933100...

result:

wrong answer 46th numbers differ - expected: '-11.14286', found: '-9.51084', error = '0.14646'