QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445869 | #6763. Triangle Pendant | liuhengxi | AC ✓ | 1ms | 2152kb | C++14 | 6.5kb | 2024-06-16 16:13:25 | 2024-06-16 16:13:25 |
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();}
};
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)));
}
};
void h1(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc,double &ans)
{
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;
if((d-c).len()>lc+eps)return;
if((o-d)*g<ans)ans=(o-d)*g,ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
}
void h2(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc,double &ans)
{
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;
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;
vec2 g=(d-o).norm();
if((o-d)*g<ans)ans=(o-d)*g,ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
}
void h3(double la,double lb,double lc,double bc,double ac,double ab,double &ansa,double &ansb,double &ansc,double &ans)
{
vec3 a,b,c;
{
vec2 a2(0,0),b2(ab,0);
pair<bool,pair<vec2,vec2>> cd=circle(a2,ac)&circle(b2,bc);
if(!cd.first)return;
vec2 c2=cd.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;
pair<bool,circle3d> sab=sphere(a,la)&sphere(b,lb);
if(!sab.first)return;
pair<bool,pair<vec3,vec3>> abc=sab.second&sphere(c,lc);
if(!abc.first)return;
vec3 d=abc.second.first;
vec3 g=(d-o).norm();
if((o-d)*g<ans)ans=(o-d)*g,ansa=(a-d)*g,ansb=(b-d)*g,ansc=(c-d)*g;
}
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;
}
double ansa,ansb,ansc,ans=1e18;
h1(la,lb,lc,bc,ca,ab,ansa,ansb,ansc,ans);
h1(lb,lc,la,ca,ab,bc,ansb,ansc,ansa,ans);
h1(lc,la,lb,ab,bc,ca,ansc,ansa,ansb,ans);
h2(la,lb,lc,bc,ca,ab,ansa,ansb,ansc,ans);
h2(lb,lc,la,ca,ab,bc,ansb,ansc,ansa,ans);
h2(lc,la,lb,ab,bc,ca,ansc,ansa,ansb,ans);
h3(la,lb,lc,bc,ca,ab,ansa,ansb,ansc,ans);
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: 1996kb
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: 0
Accepted
time: 1ms
memory: 1996kb
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:
ok 3000 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 1940kb
input:
1000 33 73 79 36 44 48 96 66 45 9 13 14 81 64 9 50 30 26 59 64 65 39 44 13 47 63 7 20 11 27 36 20 52 13 22 20 20 30 29 12 2 12 46 36 41 34 28 39 97 54 70 16 14 5 79 8 97 41 24 18 95 83 59 47 15 50 85 78 67 22 13 17 96 32 70 32 15 18 27 34 76 38 13 29 47 86 95 42 17 34 41 50 50 25 33 22 82 42 81 18 4...
output:
-32.015847290 -69.684039777 -75.638061984 -56.241370960 -51.194224815 -45.000000000 -37.905135500 -58.350854686 -9.000000000 -56.487522083 -62.826241045 -58.955695838 -7.960896812 -23.730909201 -7.000000000 -33.948706405 -19.875088175 -30.482883389 -19.910393653 -29.531609478 -21.235135018 -42.01981...
result:
ok 3000 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 2024kb
input:
1000 171 722 964 22 53 44 379 126 423 98 56 54 233 473 879 86 44 48 159 864 365 39 44 63 847 363 207 70 11 77 736 920 652 13 72 70 318 278 347 44 87 66 691 693 1000 64 50 19 879 8 297 91 74 68 536 888 163 33 44 27 495 83 959 97 65 100 968 643 337 32 61 46 204 797 870 52 62 59 885 978 167 72 63 17 22...
output:
-171.000000000 -213.850392599 -223.049554714 -177.405405405 -126.000000000 -222.594594595 -233.000000000 -255.050679634 -243.873475632 -159.000000000 -219.738578713 -199.696129351 -201.807639006 -276.325035973 -207.000000000 -723.006627426 -657.190485380 -652.000000000 -314.471872942 -277.893389205 ...
result:
ok 3000 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 2152kb
input:
1000 501 94 77 81 461 510 196 366 645 209 313 464 159 864 365 439 44 463 359 57 440 288 429 255 318 278 347 444 487 466 520 930 929 312 302 162 691 693 1000 564 250 519 33 292 661 856 572 306 410 665 850 503 313 592 947 186 395 292 817 634 466 581 266 563 125 647 672 653 583 469 216 496 554 457 945 ...
output:
-484.158538588 -22.705846490 -57.153345140 -52.426107263 -307.221896671 -309.334793607 -159.000000000 -620.756001523 -187.028645031 -197.471099289 -57.000000000 -251.038990245 -149.368244210 -117.560921904 -228.035479087 -520.000000000 -617.864529288 -793.015505224 -665.655350473 -609.122451851 -912...
result:
ok 3000 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 2004kb
input:
1000 79 26 423 98 56 54 33 473 79 86 44 48 59 64 365 39 44 63 95 83 959 97 65 100 4 97 870 52 62 59 405 53 8 11 66 75 96 3 407 45 46 67 57 847 5 38 42 72 77 173 16 68 47 53 54 57 945 80 52 83 795 18 100 67 56 72 67 42 748 48 3 50 29 35 566 52 38 18 23 56 116 35 37 15 800 12 62 54 99 74 7 696 95 38 3...
output:
-77.245731658 -25.995970870 -122.739840058 -33.000000000 -55.050679634 -43.873475632 -49.837583793 -55.920611549 -80.004560518 -83.888685266 -63.594872347 -138.120730907 -4.000000000 -56.988277918 -60.309480522 -73.548782107 -0.148704840 -8.000000000 -67.024188977 -3.000000000 -43.436329880 -27.1083...
result:
ok 3000 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 1952kb
input:
1000 171 722 64 22 53 44 379 26 423 98 56 54 233 473 79 86 44 48 381 864 9 100 80 76 159 64 365 39 44 63 847 63 207 70 11 77 189 410 33 78 87 17 736 920 52 13 72 70 318 278 47 44 87 66 91 693 1000 64 50 19 879 8 297 91 74 68 536 888 63 33 44 27 95 83 959 97 65 100 968 643 37 32 61 46 4 797 870 52 62...
output:
-115.143181364 -81.047727121 -64.000000000 -77.405405405 -26.000000000 -122.594594595 -121.609344453 -164.296871190 -79.000000000 -80.245304604 -102.144476101 -9.000000000 -124.420643288 -64.000000000 -98.679304136 -139.883294367 -63.000000000 -132.871603336 -119.701533446 -110.666955018 -33.0000000...
result:
ok 3000 numbers