#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 305;
#define int ll
const int inf = 1ll << 55;
int R, C, n;
vector<pair<int,int>> loc;
bool can_cover(int ul, int dl, int al, int bl) {
vector<vector<int>> pf_sum(50, vector<int> (50) );
for (auto [x, y] : loc) {
int A = y - ul, B = y + dl;
int C = x - bl, D = x + al;
chmax(A, 1ll);
chmax(C, 1ll);
chmin(D, R);
chmin(B, ::C);
++pf_sum[C][A];
--pf_sum[D+1][A];
--pf_sum[C][B+1];
++pf_sum[D+1][B+1];
}
for (int i = 1;i <= R;++i) {
for (int j = 1;j <= C;++j) {
pf_sum[i][j] += pf_sum[i-1][j] + pf_sum[i][j-1] - pf_sum[i-1][j-1];
if (pf_sum[i][j] == 0) return false;
}
}
return true;
}
int cal_up(int ul) {
int dnmn = 0;
{
vector<int> ys;
for (auto [x, y] : loc)
ys.pb(y - ul);
sort(AI(ys));
int lst_end = 0;
for (int y : ys) {
chmax(dnmn, y - 1 - lst_end);
lst_end = y + ul;
}
chmax(dnmn, C - lst_end);
}
vector<vector<tuple<int,int,int>>> op2, must;
vector<int> sep;
DE(ul);
auto all_op = [&]() {
op2.pb();
must.pb();
sort(AI(loc));
for (int i = 0;i < n;++i) {
auto [x, y] = loc[i];
DE(" gen ------------ ", x, y);
auto segmx = [&](int l, int r, int v) {
chmax(l, dnmn);
chmin(r, C);
if (l > r) return;
DE("segmx", l, r, v - x - 1);
sep.pb(l), sep.pb(r+1);
op2.back().pb(l, r+1, v - x - 1);
};
auto allmx = [&](int l, int r, int v) {
chmax(l, dnmn);
chmin(r, C);
if (l > r) return;
DE("mustmx", l, r, v - x - 1);
sep.pb(l), sep.pb(r+1);
must.back().pb(l, r+1, v - x - 1);
};
set<int> ys;
ys.insert(-inf);
ys.insert(inf);
int nl = 1, nr = C;
for (int j = i+1;j < n;++j) {
auto [cx, cy] = loc[j];
if (cx == x) continue;
if (cy <= y) chmax(nl, cy + 1);
if (cy >= y) chmin(nr, cy - ul - 1);
DE(cx, cy);
auto it = ys.lower_bound(cy);
int ly = *prev(it), ry = *it; ys.insert(cy);
int s = -1, e = min(C - ly - 1, (ry - ul - 1) - ly - 1);
if (y <= ly || y >= ry) continue;
if (cy >= y) s = max<ll>(0, cy - ul - y);
else s = max<ll>(0, y - ul - cy);
segmx(s, e, cx);
}
DE(nl, nr);
if (nl > nr) continue;
if (nl == 1) allmx(0, C, R + 1);
else if (nl <= nr) allmx(0, nr - nl, R + 1);
}
DE(op2.size());
for (auto [l, r, v] : op2.back()) {
DE(l, r, v);
}
};
all_op();
for (auto &[x, y] : loc)
x = R - x + 1;
all_op();
for (auto &[x, y] : loc)
x = R - x + 1;
sep.pb(C+1);
sort(AI(sep)); sep.erase(unique(AI(sep)), end(sep));
priority_queue<pair<int,int>> pq[2], pq2[2];
sort(AI(op2[0]));
sort(AI(op2[1]));
sort(AI(must[0]));
sort(AI(must[1]));
int h[2]{}, h2[2]{};
int res = inf;
for (int i = 0;i+1 < sep.size();++i) {
auto add_in = [&](auto &pq, auto &op, int &i) {
for (;i < op.size();++i) {
auto [l, r, v] = op[i];
if (l > sep[i]) break;
pq.emplace(v, r);
}
};
auto pops = [&](auto &pq) -> ll{
while (pq.size() && pq.top().second <= sep[i])
pq.pop();
return pq.size() ? pq.top().first : 0;
};
add_in(pq[0], op2[0], h[0]);
add_in(pq[1], op2[1], h[1]);
add_in(pq2[0], must[0], h2[0]);
add_in(pq2[1], must[1], h2[1]);
DE(sep[i], ul,
max(pops(pq[0]), pops(pq[1])), pops(pq2[0]) + pops(pq2[1]));
int ld = pops(pq2[0]), rd = max(pops(pq2[1]), max(pops(pq[0]), pops(pq[1])) - ld), dn = sep[i];
assert(!can_cover(ld-1, rd+1));
//rd = pops(pq2[1]);
//assert(can_cover(ld, rd, ul, dn));
//assert(can_cover(ul, sep[i], ld, rd));
// assert(!can_cover(ul, sep[i], ld-1, rd));
// assert(!can_cover(ul, sep[i], ld, rd-1));
chmin(res, sep[i] + ul +
max({pops(pq[0]), pops(pq[1]), pops(pq2[0]) + pops(pq2[1])}));
}
DE(ul, res);
return res;
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> R >> C >> n; loc.resize(n);
for (auto &[x, y] : loc) {
cin >> x >> y;
}
sort(AI(loc));
int res = inf;
vector<int> ys;
for (auto [x, y] : loc) ys.pb(y);
// for (int ul = 0;ul <= C;++ul) for (int dl = 0;dl <= C;++dl) {
// int A = R, B = R;
// while (B > 0 && can_cover(ul, dl, A, B-1)) --B;
// while (A > 0 && can_cover(ul, dl, A-1, B)) --A;
// if (can_cover(ul, dl, A, B))
// chmin(res, ul + dl + A + B);
// }
// location should be the same
for (int y : ys) {
chmin(res, cal_up(y - 1));
}
cout << res << '\n';
}
Compilation message
cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:68:2: note: in expansion of macro 'DE'
68 | DE(ul);
| ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:77:4: note: in expansion of macro 'DE'
77 | DE(" gen ------------ ", x, y);
| ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:82:5: note: in expansion of macro 'DE'
82 | DE("segmx", l, r, v - x - 1);
| ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:91:5: note: in expansion of macro 'DE'
91 | DE("mustmx", l, r, v - x - 1);
| ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:109:5: note: in expansion of macro 'DE'
109 | DE(cx, cy);
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:119:4: note: in expansion of macro 'DE'
119 | DE(nl, nr);
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:127:3: note: in expansion of macro 'DE'
127 | DE(op2.size());
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:129:4: note: in expansion of macro 'DE'
129 | DE(l, r, v);
| ^~
cultivation.cpp:128:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
128 | for (auto [l, r, v] : op2.back()) {
| ^~~~~~~~~
cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:154:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0;i+1 < sep.size();++i) {
| ~~~~^~~~~~~~~~~~
cultivation.cpp: In instantiation of 'cal_up(ll)::<lambda(auto:23&, auto:24&, ll&)> [with auto:23 = std::priority_queue<std::pair<long long int, long long int> >; auto:24 = std::vector<std::tuple<long long int, long long int, long long int> >; ll = long long int]':
cultivation.cpp:168:29: required from here
cultivation.cpp:156:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for (;i < op.size();++i) {
| ~~^~~~~~~~~~~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:174:3: note: in expansion of macro 'DE'
174 | DE(sep[i], ul,
| ^~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from cultivation.cpp:1:
cultivation.cpp:179:31: error: too few arguments to function 'bool can_cover(ll, ll, ll, ll)'
179 | assert(!can_cover(ld-1, rd+1));
| ^
cultivation.cpp:25:6: note: declared here
25 | bool can_cover(int ul, int dl, int al, int bl) {
| ^~~~~~~~~
cultivation.cpp:177:86: warning: unused variable 'dn' [-Wunused-variable]
177 | int ld = pops(pq2[0]), rd = max(pops(pq2[1]), max(pops(pq[0]), pops(pq[1])) - ld), dn = sep[i];
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:192:2: note: in expansion of macro 'DE'
192 | DE(ul, res);
| ^~
