QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445860 | #6763. Triangle Pendant | liuhengxi | WA | 0ms | 2148kb | C++14 | 6.5kb | 2024-06-16 15:55:44 | 2024-06-16 15:55:45 |
Judging History
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'