QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#553558 | #8677. Carl’s Vacation | RngBased# | WA | 4ms | 3872kb | C++17 | 2.6kb | 2024-09-08 15:26:09 | 2024-09-08 15:26:10 |
Judging History
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'