QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402123#3219. ManhattanI_Love_Sonechka#WA 460ms3876kbC++172.8kb2024-04-29 22:17:312024-04-29 22:17:33

Judging History

This is the latest submission verdict.

  • [2024-04-29 22:17:33]
  • Judged
  • Verdict: WA
  • Time: 460ms
  • Memory: 3876kb
  • [2024-04-29 22:17:31]
  • Submitted

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 l = 0, r = 0.5;
	for(int i = 0; i < 60; ++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(12);
	ld res = 0;
	ld eps2 = 1e-12;
	for(int i = 0; i < 100000; ++i) {
		ld point = l + (i-100000/2) * eps2;
		if(point < 0) {
			continue;
		}
		if(point > 1) {
			continue;
		}
		res = max(res, f(point));
	}
	for(int i = 0; i < 100000; ++i) {
		ld point = r + (i-100000/2) * eps2;
		if(point < 0) {
			continue;
		}
		if(point > 1) {
			continue;
		}
		res = max(res, f(point));
	}
	cout << res << "\n";
}

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: 460ms
memory: 3876kb

input:

1.414

output:

1.999697954384

result:

wrong answer 1st numbers differ - expected: '2.0000000', found: '1.9996980', error = '0.0001510'