QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780671 | #8677. Carl’s Vacation | ucup-team5217# | AC ✓ | 7ms | 3976kb | C++23 | 4.2kb | 2024-11-25 12:16:03 | 2024-11-25 12:16:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ld= long double;
struct vec{
ld x,y;
vec(ld a=0,ld b=0){x=a,y=b;}
vec operator+(const vec a)const {
return {x+a.x,y+a.y};
}
vec operator-(const vec a)const {
return {x-a.x,y-a.y};
}
vec operator*(ld a)const {
return {x*a,y*a};
}
ld operator*(const vec a)const {
return x*a.x+y*a.y;
}
ld operator^(const vec a)const {
return x*a.y-y*a.x;
}
ld len(){
return sqrt(x*x+y*y);
}
ld len2(){
return (x*x+y*y);
}
};
const ld eps=1e-12;
bool onray(vec a,vec v,vec c){
if(fabs(((c-a)^v))<=eps&&((c-a)*v)>=eps) return true;
return false;
}
int sgn(ld x){
if(x>eps) return 1;
if(fabs(x)<=eps) return 0;
return -1;
}
// ld check(vec a,vec v,vec c,vec d){
// if(on_ray(a,v,c)||on_ray(a,v,d)) return true;
// return sgn(v^(c-a))*sgn(v^(d-a))<0&&sgn((a-d)^(c-d))!=sgn(v^(c-d));
// }
bool online(vec a,vec b,vec c){
if(((c-a)*(c-b))<=-eps&&fabs(((c-a)^(c-b)))<eps) return true;
return false;
}
ld check(vec a,vec b,vec c,vec d){
if(online(a,b,c)||online(a,b,d)||online(c,d,a)||online(c,d,b)) return true;
return sgn((c-b)^(a-b))*sgn((d-b)^(a-b))<-eps&&sgn((a-d)^(c-d))*sgn((b-d)^(c-d))<-eps;
}
ld get_len(vec a,vec v,vec c){
assert(v.len()>=eps);
return ((c-a)^v)/(v.len());
}
struct poly{
ld x1,y1,x2,y2,h;
void read(){
cin>>x1>>y1>>x2>>y2>>h;
}
pair<vec,vec> get(int mo){
if(mo==0) return make_pair(vec(x1,y1),vec(x2,y2));
if(mo==1) return make_pair(vec(x2,y2),vec(x2-(y2-y1),y2+(x2-x1)));
if(mo==2) return make_pair(vec(x2-(y2-y1),y2+(x2-x1)),vec(x1-(y2-y1),y1+(x2-x1)));
if(mo==3) return make_pair(vec(x1-(y2-y1),y1+(x2-x1)),vec(x1,y1));
}
vec getmid(){
return vec(x1+x2,y1+y2)*0.5+vec(-(y2-y1)/2,(x2-x1)/2);
}
};
void solve(void) {
poly a,b;
a.read(),b.read();
ld ans=-1;
for(int i=0;i<4;i++){
pair<vec,vec> p=a.get(i);
for(int j=0;j<4;j++){
ld lo=0,ro=1;
auto get=[&](vec x)->ld {
pair<vec,vec> q=b.get(j);
ld lh=0,rh=1;
bool fl=0,fr=0;
for(int k=0;k<4;k++){
if(k==j) continue;
pair<vec,vec> z=b.get(k);
if(check(x,q.first,z.first,z.second)) fl=1;
}
for(int k=0;k<4;k++){
if(k==j) continue;
pair<vec,vec> z=b.get(k);
if(check(x,q.second,z.first,z.second)) fr=1;
}
if(fl&&fr) return -1;
if(fr&&!fl) swap(q.first,q.second);
auto res=[&](vec y)->ld {
// cerr<<(a.getmid()-x).len2()<<' '<<a.h*a.h<<' '<<(b.getmid()-y).len2()<<' '<<b.h*b.h<<' '<<(x-y).len()<<'\n';
return sqrt((a.getmid()-x).len2()+a.h*a.h)+sqrt((b.getmid()-y).len2()+b.h*b.h)+(x-y).len();
};
while(fabs(lh-rh)>eps){
ld midl=(2*lh+rh)/3;
ld midr=(lh+2*rh)/3;
ld len1=res(q.first+(q.second-q.first)*midl);
ld len2=res(q.first+(q.second-q.first)*midr);
if(len1>=len2) lh=midl;
else rh=midr;
}
return res(q.first+(q.second-q.first)*lh);
};
while(fabs(lo-ro)>eps){
ld midl=(2*lo+ro)/3;
ld midr=(lo+2*ro)/3;
ld len1=get(p.first+(p.second-p.first)*midl);
ld len2=get(p.first+(p.second-p.first)*midr);
if(len1>=len2) lo=midl;
else ro=midr;
}
ld req=get(p.first+(p.second-p.first)*lo);
// cerr<<req<<' '<<i<<' '<<j<<'\n';
if(req!=-1&&(ans==-1||ans>req)) ans=req;
}
}
cout<<setprecision(12)<<ans<<'\n';
return;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int _ = 1;
while (_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 3904kb
input:
1 0 0 0 10000 99999 10000 10000 10000 10000
output:
76118.7000492
result:
ok found '76118.7000492', expected '76118.7000492', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
10000 10000 10000 0 10000 0 0 0 10000 10000
output:
32360.679775
result:
ok found '32360.6797750', expected '32360.6797750', error '0.0000000'
Test #3:
score: 0
Accepted
time: 5ms
memory: 3848kb
input:
0 0 100 100 20 0 0 -5 -5 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3856kb
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: 5ms
memory: 3848kb
input:
0 0 100 100 20 100 100 105 95 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #6:
score: 0
Accepted
time: 5ms
memory: 3912kb
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: 5ms
memory: 3916kb
input:
0 0 100 100 20 200 0 205 5 2
output:
224.528035157
result:
ok found '224.5280352', expected '224.5280352', error '0.0000000'
Test #8:
score: 0
Accepted
time: 5ms
memory: 3848kb
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: 5ms
memory: 3868kb
input:
0 0 100 100 20 -100 100 -105 105 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #10:
score: 0
Accepted
time: 5ms
memory: 3896kb
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: 5ms
memory: 3908kb
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: 5ms
memory: 3916kb
input:
0 0 30 0 20 50 20 80 20 140
output:
186.874948276
result:
ok found '186.8749483', expected '186.8749483', error '0.0000000'
Test #13:
score: 0
Accepted
time: 5ms
memory: 3856kb
input:
0 0 30 0 140 50 20 80 20 140
output:
302.264953761
result:
ok found '302.2649538', expected '302.2649538', error '0.0000000'
Test #14:
score: 0
Accepted
time: 5ms
memory: 3716kb
input:
0 0 30 0 500 50 20 80 20 140
output:
661.328793005
result:
ok found '661.3287930', expected '661.3287930', error '0.0000000'
Test #15:
score: 0
Accepted
time: 5ms
memory: 3856kb
input:
0 0 30 0 500 50 20 80 20 500
output:
1020.64587196
result:
ok found '1020.6458720', expected '1020.6458720', error '0.0000000'
Test #16:
score: 0
Accepted
time: 5ms
memory: 3920kb
input:
0 0 30 0 500 50 20 80 20 2000
output:
2520.36147375
result:
ok found '2520.3614738', expected '2520.3614737', error '0.0000000'
Test #17:
score: 0
Accepted
time: 5ms
memory: 3916kb
input:
1137 -1096 229 -599 6253 5792 -405 3433 -9660 2912
output:
16631.2672046
result:
ok found '16631.2672046', expected '16631.2672046', error '0.0000000'
Test #18:
score: 0
Accepted
time: 5ms
memory: 3908kb
input:
-1458 4365 -759 -5184 408 8891 -5111 2941 -8564 6966
output:
14848.0979672
result:
ok found '14848.0979672', expected '14848.0979672', error '0.0000000'
Test #19:
score: 0
Accepted
time: 5ms
memory: 3900kb
input:
2289 1693 -2539 850 7414 -4989 3660 8091 2109 6915
output:
18844.4706205
result:
ok found '18844.4706205', expected '18844.4706205', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
5431 8457 6717 -6624 2204 -5504 -5607 4032 -674 7792
output:
20847.8621668
result:
ok found '20847.8621668', expected '20847.8621668', error '0.0000000'
Test #21:
score: 0
Accepted
time: 5ms
memory: 3920kb
input:
4274 -9998 -3313 -2647 4590 -792 1334 5701 -8048 3257
output:
16956.4834718
result:
ok found '16956.4834718', expected '16956.4834718', error '0.0000000'
Test #22:
score: 0
Accepted
time: 5ms
memory: 3848kb
input:
-1563 -4648 1926 -2970 5843 -1600 9113 -1007 5823 7516
output:
19666.6200193
result:
ok found '19666.6200193', expected '19666.6200193', error '0.0000000'
Test #23:
score: 0
Accepted
time: 5ms
memory: 3868kb
input:
-6957 -1204 -2026 2849 1571 9178 1160 -3263 -6525 9297
output:
22798.2691656
result:
ok found '22798.2691656', expected '22798.2691656', error '0.0000000'
Test #24:
score: 0
Accepted
time: 5ms
memory: 3868kb
input:
-5254 4877 5836 -1945 4282 8106 -8783 7076 -2291 6168
output:
17820.1271049
result:
ok found '17820.1271049', expected '17820.1271049', error '0.0000000'
Test #25:
score: 0
Accepted
time: 6ms
memory: 3720kb
input:
2278 -7979 -200 -9432 528 -8604 1343 -5214 2428 8005
output:
22690.4150724
result:
ok found '22690.4150724', expected '22690.4150724', error '0.0000000'
Test #26:
score: 0
Accepted
time: 5ms
memory: 3920kb
input:
5003 277 737 -3626 2886 3492 4353 -446 5788 2426
output:
10058.3916192
result:
ok found '10058.3916192', expected '10058.3916192', error '0.0000000'
Test #27:
score: 0
Accepted
time: 5ms
memory: 3968kb
input:
-6582 -2629 -1742 6935 5531 -2010 1455 1794 -3461 9066
output:
20018.3757267
result:
ok found '20018.3757267', expected '20018.3757267', error '0.0000000'
Test #28:
score: 0
Accepted
time: 6ms
memory: 3888kb
input:
-8174 -1075 -6736 -2685 6615 -2151 4184 -1716 -308 5064
output:
16260.3532322
result:
ok found '16260.3532322', expected '16260.3532322', error '0.0000000'
Test #29:
score: 0
Accepted
time: 5ms
memory: 3852kb
input:
5291 1243 8982 5204 8450 -1177 -5306 -1390 2460 8858
output:
23316.8500583
result:
ok found '23316.8500583', expected '23316.8500583', error '0.0000000'
Test #30:
score: 0
Accepted
time: 5ms
memory: 3948kb
input:
-4229 2060 9017 -2659 5812 9887 -9973 5460 -2671 4205
output:
18310.3049216
result:
ok found '18310.3049216', expected '18310.3049216', error '0.0000000'
Test #31:
score: 0
Accepted
time: 4ms
memory: 3844kb
input:
0 0 8 0 3 0 8 8 8 3
output:
10
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
0 0 8 0 2 8 8 16 8 2
output:
12
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #33:
score: 0
Accepted
time: 6ms
memory: 3856kb
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: 3ms
memory: 3864kb
input:
0 0 8 0 100000 10 10 18 10 100000
output:
200002.828747
result:
ok found '200002.8287470', expected '200002.8287471', error '0.0000000'
Test #35:
score: 0
Accepted
time: 5ms
memory: 3932kb
input:
51412 80788 39091 71527 97605 6327 44899 20415 -12571 86627
output:
194757.486833
result:
ok found '194757.4868330', expected '194757.4868334', error '0.0000000'
Test #36:
score: 0
Accepted
time: 5ms
memory: 3856kb
input:
-43347 56743 17244 83573 86143 -90081 -3018 -22063 -95528 26489
output:
179973.341845
result:
ok found '179973.3418450', expected '179973.3418452', error '0.0000000'
Test #37:
score: 0
Accepted
time: 6ms
memory: 3864kb
input:
88637 -28248 308 -92620 47395 -57673 62668 -66785 923 49207
output:
210116.821817
result:
ok found '210116.8218170', expected '210116.8218173', error '0.0000000'
Test #38:
score: 0
Accepted
time: 6ms
memory: 3976kb
input:
59768 12643 57116 -71451 64957 -43638 42191 -37837 9851 1875
output:
171578.651505
result:
ok found '171578.6515050', expected '171578.6515053', error '0.0000000'
Test #39:
score: 0
Accepted
time: 5ms
memory: 3716kb
input:
-46206 -30845 -28470 3652 33497 74620 -92045 75046 -19320 48537
output:
147174.131715
result:
ok found '147174.1317150', expected '147174.1317146', error '0.0000000'
Test #40:
score: 0
Accepted
time: 5ms
memory: 3840kb
input:
65899 65734 27624 70256 81635 -97389 -56422 -91684 -53179 88643
output:
317109.421797
result:
ok found '317109.4217970', expected '317109.4217968', error '0.0000000'
Test #41:
score: 0
Accepted
time: 5ms
memory: 3856kb
input:
-25117 -50391 569 -34721 73972 -90107 -83510 -46359 -95477 83257
output:
174084.670254
result:
ok found '174084.6702540', expected '174084.6702542', error '0.0000000'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3972kb
input:
6832 -56636 7968 -59867 82961 6289 -49692 -56413 -38910 90946
output:
184208.611888
result:
ok found '184208.6118880', expected '184208.6118875', error '0.0000000'
Test #43:
score: 0
Accepted
time: 4ms
memory: 3840kb
input:
-100000 -100000 -100000 100000 100000 100000 100000 100000 -100000 100000
output:
482842.712475
result:
ok found '482842.7124750', expected '482842.7124746', error '0.0000000'
Test #44:
score: 0
Accepted
time: 7ms
memory: 3720kb
input:
-79878 -52149 -90171 -65032 95613 -22921 39940 69440 26987 94207
output:
319596.971758
result:
ok found '319596.9717580', expected '319596.9717576', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed