QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780627#8677. Carl’s Vacationucup-team5217#WA 53ms3984kbC++233.9kb2024-11-25 11:58:522024-11-25 11:58:53

Judging History

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

  • [2024-11-25 11:58:53]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:3984kb
  • [2024-11-25 11:58:52]
  • 提交

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++){
            pair<vec,vec> q=b.get(j);
            ld lo=0,ro=1;
            auto get=[&](vec x)->ld {
                ld lh=0,rh=1;
                auto res=[&](vec y)->ld {
                    for(int k=0;k<4;k++){
                        if(k==j)    continue;
                        pair<vec,vec> z=b.get(k);
                        if(check(x,y,z.first,z.second))  return 1e30;
                    }
                    // 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: 43ms
memory: 3916kb

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: 34ms
memory: 3860kb

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: 50ms
memory: 3732kb

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: -100
Wrong Answer
time: 53ms
memory: 3984kb

input:

0 0 100 100 20
23 23 18 18 2

output:

126.972542157

result:

wrong answer 1st numbers differ - expected: '88.0567571', found: '126.9725422', error = '0.4419398'