#include "bits/stdc++.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
const ll N = 25;
ll n, r, c, x[N], y[N];
long long ans = 1e18;
vll cup;
long long f(ll up, ll dn) {
long long mx = 0, L = 0, R = 0;
vector<ll> cp{0, r - 1};
// vector<array<ll, 3>> scan;
for (ll i = 0; i < n; i++) {
// scan.push_back({max(0, x[i] - cup[up]), 1, y[i]});
// scan.push_back({min(r, x[i] + cup[dn] + 1), -1, y[i]});
cp.push_back(min(r - 1, max(0, x[i] - cup[up] + 0)));
cp.push_back(max(0, min(r - 1, x[i] + cup[dn] + 1)));
}
// sort(scan.begin(), scan.end());
sort(cp.begin(), cp.end());
cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
for (ll p = 0; p < cp.size(); p++) {
vll a;
for (ll i = 0; i < n; i++) if (x[i] - cup[up] <= cp[p] && x[i] + cup[dn] >= cp[p]) a.push_back(y[i]);
sort(a.begin(), a.end());
if (!a.size()) mx = 1e18;
else {
L = max(L, (long long) a[0]), R = max(R, (long long) c - a.back() - 1);
for (int i = 0; i < a.size() - 1; i++) mx = max(mx, (long long) a[i + 1] - a[i] - 1);
}
}
return max(mx, L + R) + cup[dn] + cup[up];
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> r >> c >> n;
for (ll i = 0; i < n; i++) cin >> x[i] >> y[i], x[i]--, y[i]--;
cup.push_back(0);
for (ll i = 0; i < n; i++) {
cup.push_back(x[i]);
cup.push_back(r - x[i] - 1);
for (ll j = i + 1; j < n; j++) {
cup.push_back(abs(x[i] - x[j]));
if (x[i] != x[j]) cup.push_back(abs(x[i] - x[j]) - 1);
}
}
sort(cup.begin(), cup.end());
cup.resize(unique(cup.begin(), cup.end()) - cup.begin());
ll xl = 0, xr = 0, xmn = 0;
vll X;
for (ll i = 0; i < n; i++) X.push_back(x[i]);
sort(X.begin(), X.end());
xl = X[0], xr = c - 1 - X[n - 1];
for (int i = 1; i < X.size(); i++) xmn = max(xmn, X[i] - X[i - 1]);
for (ll up = 0; up < cup.size(); up++) {
if (cup[up] < xl) continue;
ll l1 = 0, r1 = cup.size() - 1;
while (l1 + 2 < r1) {
ll ml = (l1 + r1) / 2;
ll mr = ml + 1;
if (cup[ml] < xr || (cup[ml] + cup[up] < xmn) || f(up, ml) > f(up, mr)) l1 = ml;
else r1 = mr;
}
for (ll dn = l1; dn <= r1; dn++) ans = min(ans, f(up, dn));
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |