This repository has been archived by the owner on Feb 11, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
bzoj1052.cpp
93 lines (85 loc) · 1.94 KB
/
bzoj1052.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N = 20009;
const int INF = 2e9;
int n;
int x[N], y[N];
int cov[N];
inline bool in(int a, int b, int c)
{
return b <= a && a <= c;
}
bool cover(int len, int d)
{
bool flag = true;
int lx = INF, ly = INF;
int rx = -INF, ry = -INF;
for(int i = 1; i <= n; ++i)
if(!cov[i])
{
lx = min(lx, x[i]), rx = max(rx, x[i]);
ly = min(ly, y[i]), ry = max(ry, y[i]);
flag = false;
}
if(!d) return flag;
for(int i = 1; i <= n; ++i)
if(in(x[i], lx, lx+len) && in(y[i], ly, ly+len))
cov[i]++;
if(cover(len, d-1)) return true;
for(int i = 1; i <= n; ++i)
if(in(x[i], lx, lx+len) && in(y[i], ly, ly+len))
cov[i]--;
for(int i = 1; i <= n; ++i)
if(in(x[i], lx, lx+len) && in(y[i], ry-len, ry))
cov[i]++;
if(cover(len, d-1)) return true;
for(int i = 1; i <= n; ++i)
if(in(x[i], lx, lx+len) && in(y[i], ry-len, ry))
cov[i]--;
for(int i = 1; i <= n; ++i)
if(in(x[i], rx-len, rx) && in(y[i], ly, ly+len))
cov[i]++;
if(cover(len, d-1)) return true;
for(int i = 1; i <= n; ++i)
if(in(x[i], rx-len, rx) && in(y[i], ly, ly+len))
cov[i]--;
for(int i = 1; i <= n; ++i)
if(in(x[i], rx-len, rx) && in(y[i], ry-len, ry))
cov[i]++;
if(cover(len, d-1)) return true;
for(int i = 1; i <= n; ++i)
if(in(x[i], rx-len, rx) && in(y[i], ry-len, ry))
cov[i]--;
return false;
}
inline bool check(int len)
{
memset(cov, 0, sizeof cov);
return cover(len, 3);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1052.in", "r", stdin);
freopen("bzoj1052.out", "w", stdout);
#endif
scanf("%d", &n);
int lx = INF, ly = INF;
int rx = -INF, ry = -INF;
for(int i = 1; i <= n; ++i)
{
scanf("%d%d", x+i, y+i);
lx = min(lx, x[i]), rx = max(rx, x[i]);
ly = min(ly, y[i]), ry = max(ry, y[i]);
}
int l = 0, r = max(rx-lx, ry-ly);
while(l < r)
{
int mid = (l+r)>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
printf("%d\n", l);
return 0;
}