QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#553558#8677. Carl’s VacationRngBased#WA 4ms3872kbC++172.6kb2024-09-08 15:26:092024-09-08 15:26:10

Judging History

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

  • [2024-09-08 15:26:10]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3872kb
  • [2024-09-08 15:26:09]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second 
#define all(x) x.begin(), x.end()
using namespace std;

pdd operator+(pdd a, pdd b)
{
    return pdd(a.F + b.F, a.S + b.S);
}
pdd operator-(pdd a)
{
    return pdd(-a.F, -a.S);
}
pdd operator-(pdd a, pdd b)
{
    return a + (-b);
}
pdd operator*(pdd a, double b)
{
    return pdd(a.F * b, a.S * b);
}
pdd operator/(pdd a, double b)
{
    return pdd(a.F / b, a.S / b);
}
double dot(pdd a, pdd b)
{
    return a.F * b.F + a.S * b.S;
}
double abs2(pdd a)
{
    return dot(a, a);
}
pdd orth(pdd p)
{
    return pdd(-p.S, p.F);
}
pdd interpo(pdd p, pdd q, double t)
{
    return p * t + q * (1 - t);
}

double h1, h2;
pdd p1, q1, p2, q2;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> p1.F >> p1.S >> q1.F >> q1.S >> h1;
    cin >> p2.F >> p2.S >> q2.F >> q2.S >> h2;
    pdd v1 = q1 - p1, v2 = q2 - p2;

    pdd b1 = p1 + v1 / 2.0 + orth(v1) / 2.0;
    pdd b2 = p2 + v2 / 2.0 + orth(v2) / 2.0;
    double ans = 1e18;
    for (int i = 0; i < 4; i++)
    {        
        for (int j = 0; j < 4; j++)
        {
            const int S = 20;
            int T = 100;
            double l1 = 0, r1 = 1, l2 = 0, r2 = 1;
            while (T--)
            {
                double d1 = (r1 - l1) / S;
                double d2 = (r2 - l2) / S;
                pii best(0, 0);
                double cur = 1e18;
                for (int t1 = 0; t1 <= S; t1++)
                    for (int t2 = 0; t2 <= S; t2++)
                    {
                        pdd x = interpo(p1, q1, l1 + t1 * d1);
                        pdd y = interpo(p2, q2, l2 + t2 * d2);
                        double dis = sqrt(abs2(b1 - x) + h1 * h1) + 
                                     sqrt(abs2(x - y)) + 
                                     sqrt(abs2(b2 - y) + h2 * h2);
                        if (dis < cur)
                            cur = dis, best = pii(t1, t2);
                    }
                auto [t1, t2] = best;
                ans = min(ans, cur);
                l1 = max(0.0, l1 + (t1 - 1) * d1);
                l2 = max(0.0, l2 + (t2 - 1) * d2);
                r1 = min(1.0, l1 + (t1 + 1) * d1);
                r2 = min(1.0, l2 + (t2 + 1) * d2);
            }

            p2 = p2 + v2;
            v2 = orth(v2);
            q2 = q2 + v2;
        }
        p1 = p1 + v1;
        v1 = orth(v1);
        q1 = q1 + v1;
    }
    cout << fixed << setprecision(10) << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3832kb

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: 4ms
memory: 3872kb

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: 4ms
memory: 3832kb

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

input:

0 0 100 100 20
23 23 18 18 2

output:

88.0587394902

result:

wrong answer 1st numbers differ - expected: '88.0567571', found: '88.0587395', error = '0.0000225'