QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460369#8677. Carl’s VacationVermeilWA 34ms3824kbC++173.2kb2024-07-01 14:38:232024-07-01 14:38:23

Judging History

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

  • [2024-07-01 14:38:23]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:3824kb
  • [2024-07-01 14:38:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)x.size())
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pdd = pair<ld, ld>;


#define X first
#define Y second

//#define int long long


struct Seg{
    pdd a, b;
};


pdd getp(pdd a, pdd b, ld m){
    ld x = a.X * m + b.X * ((ld)1 - m);
    ld y = a.Y * m + b.Y * ((ld)1 - m);
    return {x, y};
}


pdd M1, M2;

ld dist(pdd a, pdd b){
    ld dx = a.X - b.X;
    ld dy = a.Y - b.Y;
    return sqrt(dx * dx + dy * dy);
}

ld ans = 1e18;
ld f(pdd p, pdd q, ld hp, ld hq){
    ld ret = dist(p, q);
    ld dp = dist(M1, p);
    ld dq = dist(M2, q);
    ret += sqrt(hp * hp + dp * dp);
    ret += sqrt(hq * hq + dq * dq);
    return ret;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<Seg> v1, v2;
    ld x1, y1, x2, y2, h1, h2, dx, dy;

    cin>>x1>>y1>>x2>>y2>>h1;
    dx = x2 - x1;
    dy = y2 - y1;
    for (int i=0;i<4;i++){
        M1.X += x1;
        M1.Y += y1;
        v1.push_back({{x1, y1}, {x1 + dx, y1 + dy}});
        x1 = x1 + dx; y1 = y1 + dy;
        swap(dx, dy); dx *= -1;
    }
    M1.X /= 4;
    M1.Y /= 4;

    cin>>x1>>y1>>x2>>y2>>h2;
    dx = x2 - x1;
    dy = y2 - y1;
    for (int i=0;i<4;i++){
        M2.X += x1;
        M2.Y += y1;
        v2.push_back({{x1, y1}, {x1 + dx, y1 + dy}});
        x1 = x1 + dx; y1 = y1 + dy;
        swap(dx, dy); dx *= -1;
    }
//    for (auto [a, b]: v2) cout<<a.X<<" "<<a.Y<<" "<<b.X<<" "<<b.Y<<endl;
    M2.X /= 4;
    M2.Y /= 4;

//    cout<<M2.X<<" "<<M2.Y<<endl;

    pdd p, q;
    for (auto [a1, b1]: v1){
        for (auto [a2, b2]: v2){
            ld lo = 0;
            ld hi = 1;
            for (int c1=0;c1<=150;c1++){
                ld m1 = (lo * 2 + hi) / 3;
                ld m2 = (lo + hi * 2) / 3;
                pdd p1 = getp(a1, b1, m1);
                pdd p2 = getp(a1, b1, m2);
                ld lo1 = 0, lo2 = 0;
                ld hi1 = 1, hi2 = 1;
                ld m11, m12, m21, m22;
                for (int c2=0;c2<=150;c2++){
                    m11 = (lo1 * 2 + hi1) / 3;
                    m12 = (lo1 + hi1 * 2) / 3;
                    m21 = (lo2 * 2 + hi2) / 3;
                    m22 = (lo2 + hi2 * 2) / 3;
                    pdd q11 = getp(a2, b2, m11);
                    pdd q12 = getp(a2, b2, m12);
                    pdd q21 = getp(a2, b2, m21);
                    pdd q22 = getp(a2, b2, m22);
                    if (f(p1, q11, h1, h2) > f(p1, q12, h1, h2)) lo1 = m11;
                    else hi1 = m12;
                    if (f(p2, q21, h1, h2) > f(p1, q22, h1, h2)) lo2 = m21;
                    else hi2 = m22;
                }
                pdd q1 = getp(a2, b2, lo1);
                pdd q2 = getp(a2, b2, lo2);
                p = p1;
                q = q1;
                if (f(p1, q1, h1, h2) > f(p2, q2, h1, h2)) lo = m1;
                else hi = m2;
            }
            ans = min(ans, f(p, q, h1, h2));
        }
    }

    cout<<fixed<<setprecision(16);
    cout<<ans<<endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 34ms
memory: 3736kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.7000492204770694

result:

ok found '76118.7000492', expected '76118.7000492', error '0.0000000'

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 3824kb

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

34009.9577087441056058

result:

wrong answer 1st numbers differ - expected: '32360.6797750', found: '34009.9577087', error = '0.0509655'