本蒟蒻没啥别的,帮我调出来给 3 个关注。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 505;
int n, m, k;
struct Node
{
int x, y;
// 横坐标,纵坐标
} node[maxn];
ll lsh[maxn * 2];
int lshtop;
struct Line
{
ll x, y1, y2, mark;
// y1 是这条竖线的上端点,y2 是下端点
} line[maxn * 2];
int linetop;
ll sgtcnt[maxn << 3], L[maxn << 3], R[maxn << 3], maxup[maxn << 3], mindw[maxn << 3];
// maxup 是最高的没覆盖点,min 是最低的没覆盖,注意这个是离散化之后的值
void build(int pos, int l, int r)
{
sgtcnt[pos]=0;
L[pos] = l;
R[pos] = r;
maxup[pos] = r;
mindw[pos] = l;
if (l == r)
{
return;
}
int mid = (l + r) >> 1;
build(pos << 1, l, mid);
build(pos << 1 | 1, mid + 1, r);
}
void pushup(int now)
{
if (sgtcnt[now])
{
maxup[now] = -5e9;
mindw[now] = 5e9;
}
else
{
if(L[now]!=R[now])
{
maxup[now] = max(maxup[now << 1], maxup[now << 1 | 1]);
mindw[now] = min(mindw[now << 1], mindw[now << 1 | 1]);
}
else
{
maxup[now]=mindw[now]=L[now];
}
}
}
void change(int now, int l, int r, int val)
{
if (l <= L[now] && R[now] <= r)
{
sgtcnt[now] += val;
pushup(now);
return;
}
if (L[now] > r || R[now] < l)
return;
int mid = (L[now] + R[now]) >> 1;
if (mid >= l)
change(now << 1, l, r, val);
if (mid < r)
change(now << 1 | 1, l, r, val);
pushup(now);
}
bool check(ll time)
{
lshtop = 0, linetop = 0;
FOR(i, 1, k)
{
lsh[++lshtop] = min(1ll*n, node[i].y + time);
lsh[++lshtop] = max(1ll, node[i].y - time);
}
sort(lsh + 1, lsh + lshtop + 1);
lshtop = unique(lsh + 1, lsh + lshtop + 1) - lsh - 1;
FOR(i, 1, k)
{
int nwy1 = lower_bound(lsh + 1, lsh + lshtop + 1, min(1ll*n, node[i].y + time)) - lsh;
int nwy2 = lower_bound(lsh + 1, lsh + lshtop + 1, max(1ll, node[i].y - time)) - lsh;
line[++linetop] = {max(1ll, node[i].x - time), nwy1, nwy2, 1};
line[++linetop] = {min(1ll*m, node[i].x + time)+1, nwy1, nwy2, -1};
}
sort(line + 1, line + linetop + 1, [&](Line &a, Line &b)
{ if(a.x!=b.x)
return a.x < b.x;
else
return a.mark>b.mark;
});
build(1, 1, lshtop);
ll maxupf = -5e9, mindwf = 5e9, maxrigf = -5e9, minleff = 5e9;
if (line[1].x > 1)
{
maxupf = n;
mindwf = 1;
minleff = 1;
maxrigf = 1;
// puts("Updated\n");
}
FOR(i, 1, linetop)
{
if(line[i].x>m)break;
change(1, line[i].y2, line[i].y1, line[i].mark);
// printf("i = %d\n",i);
// printf("line[%d].x = %d line[%d].y1 = %d line[%d].y2 = %d mark = %d\n", i, line[i].x,i,line[i].y1 ,i,line[i].y2,line[i].mark);
if (line[i].x != line[i + 1].x)
{
if (mindw[1] != 5e9)
{
maxupf = max(maxupf, lsh[maxup[1]]);
mindwf = min(mindwf, lsh[mindw[1]]);
// printf("up = %lld dw = %lld\n",lsh[maxup[1]],lsh[mindw[1]]);
maxrigf = max(maxrigf, line[i].x);
minleff = min(minleff, line[i].x);
}
}
}
if (line[linetop].x < m)
{
maxupf = n;
mindwf = 1;
maxrigf = m;
minleff = min(minleff, 1ll * m);
// puts("Updated2");
}
// printf("maxup = %lld mindw = %lld maxrig = %lld minlef = %lld\n", maxupf, mindwf, maxrigf, minleff);
return ((maxupf - mindwf + 1 <= time * 2 + 1) && (maxrigf - minleff + 1 <= time * 2 + 1));
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
FOR(i, 1, k)
{
scanf("%d%d", &node[i].x, &node[i].y);
swap(node[i].x, node[i].y);
}
int l = 0, r = 1e9;
while (l < r)
{
int mid = (l + r) >> 1;
// printf("l = %d r = %d mid = %d\n", l, r, mid);
if (check(mid))
{
r = mid;
}
else
{
l = mid + 1;
}
}
printf("%d", l);
return 0;
}