QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402090 | #3219. Manhattan | I_Love_Sonechka# | WA | 1ms | 3864kb | C++17 | 2.5kb | 2024-04-29 21:17:14 | 2024-04-29 21:17:15 |
Judging History
answer
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
// c++ short types
#define ll long long
#define vt vector
#define ld long double
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
int up(ld x) {
return ceil(x);
}
int down(int x) {
return floor(x);
}
const ld eps = 1e-6;
void solve() {
ld d; cin >> d;
auto calc = [&](ld x1, ld y1, ld x2, ld y2) {
assert(fabs(d * d - (x1 - x2) * (x1 - x2) - (y1 - y2) * (y1 - y2)) < eps);
vt<array<ld, 3>> points_1;
for(int i = 0; i < 4; ++i) {
ld x, y, dist = 0;
if(i & 1) {
x = down(x1);
} else {
x = up(x1);
}
dist += abs(x - x1);
if(i & 2) {
y = down(y1);
} else {
y = up(y1);
}
dist += abs(y - y1);
points_1.push_back({x, y, dist});
}
vt<array<ld, 3>> points_2;
for(int i = 0; i < 4; ++i) {
ld x, y, dist = 0;
if(i & 1) {
x = down(x2);
} else {
x = up(x2);
}
dist += abs(x - x2);
if(i & 2) {
y = down(y2);
} else {
y = up(y2);
}
dist += abs(y - y2);
points_2.push_back({x, y, dist});
}
ld res = 4000;
for(auto f: points_1) {
for(auto s: points_2) {
res = min(res, abs(f[0] - s[0]) + abs(f[1] - s[1]) + f[2] + s[2]);
}
}
return res;
};
auto f = [&](ld y1) {
// x1 = 0, y1 = y
// x2 in Z or y2 in Z
// x2^2 + (y1-y2)^2 = d ^ 2
ld res = -y1;
for(ld x2 = 0; x2 < 11; x2 += 1) {
if(x2 > d) {
break;
}
// (y1-y2) ^ 2 = d - x2 ^ 2;
// y1 - y2 = + sqrt(d - x2*x2)
// y1 - y2 = - sqrt(d - x2*x2)
ld sq = sqrt(d * d - x2 * x2);
res = max(res, calc(0, y1, x2, y1 - sq));
res = max(res, calc(0, y1, x2, y1 + sq));
}
for(ld y2 = 0; y2 < 11; y2 += 1) {
ld sq = d * d - (y1-y2)*(y1-y2);
if(sq < 0) {
continue;
}
sq = sqrt(sq);
// x2^2 + (y1-y2)^2 = d
// x2^2 = d ^ 2 - (y1-y2)^2
res = max(res, calc(0, y1, -sq, y2));
res = max(res, calc(0, y1, +sq, y2));
}
return res;
};
// ld res = 0;
// for(ld x = 0; x < 1; x += eps) {
// res = max(res, f(x));
// }
// cout << res << "\n";
ld l = 0, r = 0.5;
for(int i = 0; i < 200; ++i) {
ld m1 = l + (r-l) / 3;
ld m2 = r - (r-l) / 3;
if(f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
cout << fixed << setprecision(20);
cout << f(l) << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int tt = 1;
for(int t = 0; t < tt; ++t) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3864kb
input:
1.414
output:
1.99969795438422299496
result:
wrong answer 1st numbers differ - expected: '2.0000000', found: '1.9996980', error = '0.0001510'