QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#524043 | #8677. Carl’s Vacation | ucup-team052 | AC ✓ | 1ms | 3992kb | C++23 | 4.7kb | 2024-08-19 09:14:36 | 2024-08-19 09:14:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using db=long double;
const db eps=1e-9;
struct Vec
{
db x,y;
Vec(db a=0,db b=0) {x=a,y=b;}
db norm() {return x*x+y*y;}
db abs() {return sqrt(x*x+y*y);}
};
Vec operator + (Vec x,Vec y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (Vec x,Vec y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (Vec x,db y) {return Vec(x.x*y,x.y*y);}
Vec operator / (Vec x,db y) {return Vec(x.x/y,x.y/y);}
db cross(Vec x,Vec y) {return x.x*y.y-x.y*y.x;}
int sgn(db x)
{
if(x<-eps) return -1;
else if(x>eps) return 1;
else return 0;
}
int ccw(Vec x,Vec y,Vec z) {return sgn(cross(y-x,z-x));}
struct Seg
{
Vec s,t;
Seg(Vec a=0,Vec b=0) {s=a,t=b;}
Seg() {}
};
int isintersect(Seg p,Seg q)
{
if(max(p.s.x,p.t.x)<min(q.s.x,q.t.x)) return 0;
if(max(q.s.x,q.t.x)<min(p.s.x,p.t.x)) return 0;
if(max(p.s.y,p.t.y)<min(q.s.y,q.t.y)) return 0;
if(max(q.s.y,q.t.y)<min(p.s.y,p.t.y)) return 0;
if(ccw(q.s,p.s,p.t)*ccw(q.t,p.s,p.t)==1) return 0;
if(ccw(p.s,q.s,q.t)*ccw(p.t,q.s,q.t)==1) return 0;
return 1;
}
Vec r90(Vec x) {return Vec(-x.y,x.x);}
Vec a[10],b[10];
const db pi=acos(-1);
db dif(db x,db y)
{
db v=x-y;
while(v>=2*pi) v-=2*pi;
while(v<0) v+=2*pi;
if(v<pi) return v;
else return 2*pi-v;
}
void print(Vec x) {printf("%.2Lf %.2Lf\n",x.x,x.y);}
int ok1[10],ok2[10];
int main() {
#ifdef xay5421
freopen("b.in","r",stdin);
#endif
Vec a1,b1,a2,b2; db h1,h2;
cin>>a1.x>>a1.y>>b1.x>>b1.y>>h1;
cin>>a2.x>>a2.y>>b2.x>>b2.y>>h2;
a[0]=a1,a[1]=b1,a[2]=b1+r90(b1-a1),a[3]=a1+r90(b1-a1);
b[0]=a2,b[1]=b2,b[2]=b2+r90(b2-a2),b[3]=a2+r90(b2-a2);
a[4]=a[0],b[4]=b[0];
// print(a[0]),print(a[1]),print(a[2]),print(a[3]);
// print(b[0]),print(b[1]),print(b[2]),print(b[3]);
db ans=1e100;
Vec ca=(a[0]+a[2])/2,cb=(b[0]+b[2])/2;
db La=(ca.x-a[0].x)*(ca.x-a[0].x)+(ca.y-a[0].y)*(ca.y-a[0].y)+h1*h1;
db Lb=(cb.x-b[0].x)*(cb.x-b[0].x)+(cb.y-b[0].y)*(cb.y-b[0].y)+h2*h2;
// cout<<sqrt(Lb)<<endl;
db lena=sqrt(La-(a[1]-a[0]).norm()/4),lenb=sqrt(Lb-(b[1]-b[0]).norm()/4);
// cout<<lena<<" "<<lenb<<endl;
for(int i=0;i<4;i++)
{
if(isintersect(Seg(ca,cb),Seg(a[i],a[i+1]))) ok1[i]=ok1[(i+1)%4]=ok1[(i+3)%4]=1;
if(isintersect(Seg(ca,cb),Seg(b[i],b[i+1]))) ok2[i]=ok2[(i+1)%4]=ok2[(i+3)%4]=1;
}
for(int i=0;i<4;i++) if(ok1[i]) for(int j=0;j<4;j++) if(ok2[j])
{
Vec da=r90(a[i+1]-a[i]); da=da/da.abs(); da=da*lena;
Vec va=(a[i+1]+a[i])/2+da;
Vec db=r90(b[j+1]-b[j]); db=db/db.abs(); db=db*lenb;
Vec vb=(b[j+1]+b[j])/2+db;
// printf("%d %d : \n",i,j),print(va),print(vb);
// printf("%d %d %d %d\n",ccw(va,a[i],vb),ccw(va,vb,a[i+1]),ccw(vb,b[j],va),ccw(vb,va,b[j+1]));
if(!isintersect(Seg(va,vb),Seg(a[i],a[i+1]))) continue;
if(!isintersect(Seg(va,vb),Seg(b[j],b[j+1]))) continue;
if(ccw(va,a[i],vb)>=0&&ccw(va,vb,a[i+1])>=0)
{
if(ccw(vb,b[j],va)>=0&&ccw(vb,va,b[j+1])>=0)
{
ans=min(ans,(va-vb).abs());
}
}
}
auto chka=[&](int id,Vec v)
{
return ccw(a[id],a[(id+3)%4],v)<=0&&ccw(a[id],v,a[(id+1)%4])<=0;
};
auto chkb=[&](int id,Vec v)
{
return ccw(b[id],b[(id+3)%4],v)<=0&&ccw(b[id],v,b[(id+1)%4])<=0;
};
for(int i=0;i<4;i++) for(int j=0;j<4;j++)
{
if(chka(i,b[j])) continue;
if(chkb(j,a[i])) continue;
db l=sqrt(La)+sqrt(Lb)+(a[i]-b[j]).abs();
ans=min(ans,l);
}
for(int i=0;i<4;i++) if(ok1[i]) for(int j=0;j<4;j++)
{
Vec da=r90(a[i+1]-a[i]); da=da/da.abs(); da=da*lena;
Vec va=(a[i+1]+a[i])/2+da;
if(chkb(j,va)) continue;
if(!isintersect(Seg(va,b[j]),Seg(a[i],a[i+1]))) continue;
if(ccw(va,a[i],b[j])>=0&&ccw(va,b[j],a[i+1])>=0)
{
db tl=sqrt(Lb)+(va-b[j]).abs();
ans=min(ans,tl);
}
}
for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(ok2[j])
{
Vec db=r90(b[j+1]-b[j]); db=db/db.abs(); db=db*lenb;
Vec vb=(b[j+1]+b[j])/2+db;
if(chka(i,vb)) continue;
if(!isintersect(Seg(a[i],vb),Seg(b[j],b[j+1]))) continue;
if(ccw(vb,b[j],a[i])>=0&&ccw(vb,a[i],b[j+1])>=0)
{
long double tl=sqrt(La)+(vb-a[i]).abs();
ans=min(ans,tl);
}
}
printf("%.10Lf\n",ans);
return 0;
}
/*
6.40312 44.0028
0 0 :
5.00 6.40
8.09 63.91
-1 -1 -1 1
0 1 :
5.00 6.40
-11.91 25.09
-1 1 -1 1
0 2 :
5.00 6.40
26.91 5.09
1 -1 1 -1
0 3 :
5.00 6.40
46.91 43.91
1 -1 1 -1
1 0 :
3.60 5.00
8.09 63.91
1 -1 -1 1
1 1 :
3.60 5.00
-11.91 25.09
1 -1 -1 1
1 2 :
3.60 5.00
26.91 5.09
1 1 1 -1
1 3 :
3.60 5.00
46.91 43.91
1 -1 1 -1
2 0 :
5.00 3.60
8.09 63.91
1 1 -1 1
2 1 :
5.00 3.60
-11.91 25.09
1 -1 -1 1
2 2 :
5.00 3.60
26.91 5.09
-1 1 1 -1
2 3 :
5.00 3.60
46.91 43.91
-1 1 1 -1
3 0 :
6.40 5.00
8.09 63.91
-1 1 -1 1
3 1 :
6.40 5.00
-11.91 25.09
-1 1 -1 1
3 2 :
6.40 5.00
26.91 5.09
-1 -1 1 -1
3 3 :
6.40 5.00
46.91 43.91
-1 1 1 -1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3988kb
input:
1 0 0 0 10000 99999 10000 10000 10000 10000
output:
76118.7000492205
result:
ok found '76118.7000492', expected '76118.7000492', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
10000 10000 10000 0 10000 0 0 0 10000 10000
output:
32360.6797749979
result:
ok found '32360.6797750', expected '32360.6797750', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
0 0 100 100 20 0 0 -5 -5 2
output:
107.3655550790
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
0 0 100 100 20 23 23 18 18 2
output:
88.0567570506
result:
ok found '88.0567571', expected '88.0567571', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
0 0 100 100 20 100 100 105 95 2
output:
107.3655550790
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
0 0 100 100 20 44 156 49 151 2
output:
77.7045202177
result:
ok found '77.7045202', expected '77.7045202', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
0 0 100 100 20 200 0 205 5 2
output:
224.5280351568
result:
ok found '224.5280352', expected '224.5280352', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
0 0 100 100 20 -29 171 -24 176 2
output:
84.3681957983
result:
ok found '84.3681958', expected '84.3681958', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
0 0 100 100 20 -100 100 -105 105 2
output:
107.3655550790
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
0 0 100 100 20 -69 69 -74 74 2
output:
83.2946124444
result:
ok found '83.2946124', expected '83.2946124', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
0 0 30 0 20 50 20 80 20 20
output:
72.8010988928
result:
ok found '72.8010989', expected '72.8010989', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
0 0 30 0 20 50 20 80 20 140
output:
186.8749482758
result:
ok found '186.8749483', expected '186.8749483', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
0 0 30 0 140 50 20 80 20 140
output:
302.2649537612
result:
ok found '302.2649538', expected '302.2649538', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
0 0 30 0 500 50 20 80 20 140
output:
661.3287930050
result:
ok found '661.3287930', expected '661.3287930', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
0 0 30 0 500 50 20 80 20 500
output:
1020.6458719614
result:
ok found '1020.6458720', expected '1020.6458720', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
0 0 30 0 500 50 20 80 20 2000
output:
2520.3614737461
result:
ok found '2520.3614737', expected '2520.3614737', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
1137 -1096 229 -599 6253 5792 -405 3433 -9660 2912
output:
16631.2672046379
result:
ok found '16631.2672046', expected '16631.2672046', error '0.0000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
-1458 4365 -759 -5184 408 8891 -5111 2941 -8564 6966
output:
14848.0979672057
result:
ok found '14848.0979672', expected '14848.0979672', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2289 1693 -2539 850 7414 -4989 3660 8091 2109 6915
output:
18844.4706205017
result:
ok found '18844.4706205', expected '18844.4706205', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
5431 8457 6717 -6624 2204 -5504 -5607 4032 -674 7792
output:
20847.8621668110
result:
ok found '20847.8621668', expected '20847.8621668', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4274 -9998 -3313 -2647 4590 -792 1334 5701 -8048 3257
output:
16956.4834717883
result:
ok found '16956.4834718', expected '16956.4834718', error '0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
-1563 -4648 1926 -2970 5843 -1600 9113 -1007 5823 7516
output:
19666.6200192504
result:
ok found '19666.6200193', expected '19666.6200193', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
-6957 -1204 -2026 2849 1571 9178 1160 -3263 -6525 9297
output:
22798.2691656400
result:
ok found '22798.2691656', expected '22798.2691656', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
-5254 4877 5836 -1945 4282 8106 -8783 7076 -2291 6168
output:
17820.1271048619
result:
ok found '17820.1271049', expected '17820.1271049', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
2278 -7979 -200 -9432 528 -8604 1343 -5214 2428 8005
output:
22690.4150723923
result:
ok found '22690.4150724', expected '22690.4150724', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
5003 277 737 -3626 2886 3492 4353 -446 5788 2426
output:
10058.3916191793
result:
ok found '10058.3916192', expected '10058.3916192', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
-6582 -2629 -1742 6935 5531 -2010 1455 1794 -3461 9066
output:
20018.3757266857
result:
ok found '20018.3757267', expected '20018.3757267', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
-8174 -1075 -6736 -2685 6615 -2151 4184 -1716 -308 5064
output:
16260.3532322230
result:
ok found '16260.3532322', expected '16260.3532322', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5291 1243 8982 5204 8450 -1177 -5306 -1390 2460 8858
output:
23316.8500582544
result:
ok found '23316.8500583', expected '23316.8500583', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
-4229 2060 9017 -2659 5812 9887 -9973 5460 -2671 4205
output:
18310.3049215940
result:
ok found '18310.3049216', expected '18310.3049216', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
0 0 8 0 3 0 8 8 8 3
output:
10.0000000000
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
0 0 8 0 2 8 8 16 8 2
output:
12.0000000000
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
0 0 8 0 2 10 10 18 10 2
output:
14.8284271247
result:
ok found '14.8284271', expected '14.8284271', error '0.0000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
0 0 8 0 100000 10 10 18 10 100000
output:
200002.8287471247
result:
ok found '200002.8287471', expected '200002.8287471', error '0.0000000'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
51412 80788 39091 71527 97605 6327 44899 20415 -12571 86627
output:
194757.4868334289
result:
ok found '194757.4868334', expected '194757.4868334', error '0.0000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
-43347 56743 17244 83573 86143 -90081 -3018 -22063 -95528 26489
output:
179973.3418451778
result:
ok found '179973.3418452', expected '179973.3418452', error '0.0000000'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
88637 -28248 308 -92620 47395 -57673 62668 -66785 923 49207
output:
210116.8218173325
result:
ok found '210116.8218173', expected '210116.8218173', error '0.0000000'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
59768 12643 57116 -71451 64957 -43638 42191 -37837 9851 1875
output:
171578.6515053421
result:
ok found '171578.6515053', expected '171578.6515053', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
-46206 -30845 -28470 3652 33497 74620 -92045 75046 -19320 48537
output:
147174.1317146147
result:
ok found '147174.1317146', expected '147174.1317146', error '0.0000000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
65899 65734 27624 70256 81635 -97389 -56422 -91684 -53179 88643
output:
317109.4217967594
result:
ok found '317109.4217968', expected '317109.4217968', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
-25117 -50391 569 -34721 73972 -90107 -83510 -46359 -95477 83257
output:
174084.6702541819
result:
ok found '174084.6702542', expected '174084.6702542', error '0.0000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
6832 -56636 7968 -59867 82961 6289 -49692 -56413 -38910 90946
output:
184208.6118875315
result:
ok found '184208.6118875', expected '184208.6118875', error '0.0000000'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
-100000 -100000 -100000 100000 100000 100000 100000 100000 -100000 100000
output:
482842.7124746190
result:
ok found '482842.7124746', expected '482842.7124746', error '0.0000000'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
-79878 -52149 -90171 -65032 95613 -22921 39940 69440 26987 94207
output:
319596.9717576302
result:
ok found '319596.9717576', expected '319596.9717576', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed