C++ 解法, 执行用时: 64ms, 内存消耗: 1976K, 提交时间: 2023-08-12 10:19:04

/* name: std
 * author: 5ab
 * created at: 2023-02-03
 */
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <cassert>
#include <cmath>
using namespace std;

typedef long long ll;
using db = long double;

const int max_k = 100000;
const db eps = 1e-16;

int rx[max_k], ry[max_k], gx[max_k], gy[max_k], k;
pair<db, db> itv[max_k + 2];
db ans = 0;

bool validate(db x, db y, db r, int n, int m)
{
	return x - r > -eps && n - x - r > -eps && m - y - r > -eps;
}

inline db sqr(db x) { return x * x; }
inline void chmax(db& _a, db _b) { if (_a < _b) _a = _b; }
inline void chmin(db& _a, db _b) { if (_a > _b) _a = _b; }

pair<db, db> solve_equation(db a, db b, db c)
{
	if (fabs(a - 0) < eps)
		return make_pair(-c / b, -c / b);
	db delta = sqr(b) - 4 * a * c + eps;
	// cerr << a << " " << b << " " << c << endl;
	// assert(delta >= 0);
	delta = sqrt(delta);
	return make_pair((-b + delta) / (a * 2), (-b - delta) / (a * 2));
}
db get_value(db a, db b, db c, db x) { return (a * x + b) * x + c; }

void solve2(int *x, int *y, int m)
{
	db ret = m / 2.0;
	for (int i = 0; i < k; i++)
		chmin(ret, solve_equation(1, -2.0 * (x[i] + y[i]), sqr(x[i]) + sqr(y[i])).second);
	chmax(ans, ret);
}

void solve3(int *x, int *y, int n, int m)
{
	auto make_eq_param = [&](db x0, db y0, db& a, db& b, db& c) {
		a = 0.5 / y0;
		b = -x0 / y0;
		c = x0 * x0 / (2 * y0) + y0 / 2;
	};
	db pa, pb, pc, ca, cb, cc;
	int si = (y[0] == 0 ? 1 : 0);
	make_eq_param(x[si], y[si], pa, pb, pc);
	for (int i = si + 1; i < k; i++)
	{
		if (y[i] == 0)
			break;
		make_eq_param(x[i], y[i], ca, cb, cc);
		auto [ax, bx] = solve_equation(pa - ca, pb - cb, pc - cc);
		for (db sx : {ax, bx})
		{
			db sy = get_value(pa, pb, pc, sx);
			if (validate(sx, sy, sy, n, m))
				chmax(ans, sy);
		}
		pa = ca, pb = cb, pc = cc;
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
		cin >> rx[i] >> ry[i];
	if (n < m)
	{
		swap(n, m);
		swap(rx, ry);
	}
	if (rx[k - 1] < rx[0])
	{
		reverse(rx, rx + k);
		reverse(ry, ry + k);
	}
	for (int i = 0; i < k; i++)
		gx[i] = n - rx[i], gy[i] = m - ry[i];
	
	// Case 1: |(...)|
	
	int stp = 0;
	auto push_range = [&](db l, db r) {
		itv[stp++] = make_pair(l, r);
		while (stp > 1 && itv[stp - 2].second > itv[stp - 1].first)
		{
			stp--;
			chmax(itv[stp - 1].second, itv[stp].second);
			chmin(itv[stp - 1].first, itv[stp].first);
		}
	};
	
	push_range(0, m / 2.0);
	for (int i = 0; i < k; i++)
	{
		db dr = sqrt(sqr(m / 2.0) - sqr(ry[i] - m / 2.0));
		push_range(rx[i] - dr, rx[i] + dr);
	}
	push_range(n - m / 2.0, n);
	if (stp > 1)
	{
		cout << fixed << setprecision(10) << m / 2.0 << endl;
		return 0;
	}
	
	// Case 2: |__
	
	solve2(rx, ry, m);
	solve2(rx, gy, m);
	solve2(gx, gy, m);
	solve2(gx, ry, m);
	
	// Case 3: two points
	
	solve3(rx, ry, n, m);
	solve3(gy, rx, m, n);
	solve3(gx, gy, n, m);
	solve3(ry, gx, m, n);
	
	cout << fixed << setprecision(10) << ans << endl;
	
	return 0;
}
// started coding at: 02-03 20:41:07