QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780671#8677. Carl’s Vacationucup-team5217#AC ✓7ms3976kbC++234.2kb2024-11-25 12:16:032024-11-25 12:16:05

Judging History

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

  • [2024-11-25 12:16:05]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3976kb
  • [2024-11-25 12:16:03]
  • 提交

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