QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#460369 | #8677. Carl’s Vacation | Vermeil | WA | 34ms | 3824kb | C++17 | 3.2kb | 2024-07-01 14:38:23 | 2024-07-01 14:38:23 |
Judging History
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'