#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
const int MAXN = 310;
const ll INF = 1LL << 61;
ll R, C, n, L[MAXN][MAXN], L_lim[MAXN][MAXN], R_lim[MAXN][MAXN], dis[MAXN][MAXN], ans = INF;
ll Ur[MAXN], Dr[MAXN], Ul[MAXN], Dl[MAXN];
vector<pll> v;
int main() {Tie
cin >> R >> C >> n;
v.resize(n);
ll rest = 0;
for(pll &i : v)
cin >> i.F >> i.S, rest = max(rest, i.F);
vector<pll> tv = v;
sort(ALL(tv));
ll minm = 0;
for(int i = 0; i + 1 < n; i++)
minm = max(minm, tv[i + 1].F - tv[i].F - 1);
for(int i = 0; i < n; i++) {
Dl[i] = Dr[i] = Ul[i] = Ur[i] = INF;
{
ll uln = 0;
ll urn = R + 1;
ll dln = 0;
ll drn = R + 1;
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(v[i].S < v[j].S) {
if(v[i].F < v[j].F) {
drn = min(drn, v[j].F);
} else if(v[i].F > v[j].F) {
dln = max(dln, v[j].F);
} else {
Dl[i] = Dr[i] = -1;
}
} else if(v[i].S > v[j].S) {
if(v[i].F < v[j].F) {
urn = min(urn, v[j].F);
} else if(v[i].F > v[j].F) {
uln = max(uln, v[j].F);
} else {
Ul[i] = Ur[i] = -1;
}
}
}
if(Dl[i] != -1) {
if(dln != 0) {
Dr[i] = drn - dln - 1;
} else {
Dr[i] = INF;
}
if(drn != R + 1) {
Dl[i] = drn - dln - 1;
} else {
Dl[i] = INF;
}
}
if(Ul[i] != -1) {
if(uln != 0) {
Ur[i] = urn - uln - 1;
} else {
Ur[i] = INF;
}
if(urn != R + 1) {
Ul[i] = urn - uln - 1;
} else {
Ul[i] = INF;
}
}
}
for(int j = i + 1; j < n; j++) {
ll l = min(v[i].F, v[j].F);
ll r = max(v[i].F, v[j].F);
ll u = min(v[i].S, v[j].S);
ll d = max(v[i].S, v[j].S);
L[i][j] = r - l;
dis[i][j] = d - u - 1;
ll ln = 0;
ll rn = R + 1;
for(int k = 0; k < n; k++) {
if(u < v[k].S && v[k].S < d) {
if(l <= v[k].F && v[k].F <= r)
L_lim[i][j] = R_lim[i][j] = -1;
else if(v[k].F < l)
ln = max(ln, v[k].F);
else if(v[k].F > l)
rn = min(rn, v[k].F);
}
}
if(L_lim[i][j] == -1) continue;
if(rn != R + 1)
L_lim[i][j] = rn - ln - 1;
else
L_lim[i][j] = INF;
if(ln != 0)
R_lim[i][j] = rn - ln - 1;
else
R_lim[i][j] = INF;
}
}
vector<int> Lm, Rm;
for(int i = 0; i < n; i++) {
ll tmp = v[i].F - 1;
for(int j = 0; j < n; j++) {
if(v[j].S == v[i].S && v[i].F > v[j].F)
tmp = min(v[i].F - v[j].F - 1, tmp);
}
Lm.pb(tmp);
}
sort(ALL(Lm)), Lm.resize(unique(ALL(Lm)) - Lm.begin());
sort(ALL(Rm)), Rm.resize(unique(ALL(Rm)) - Rm.begin());
for(ll lm : Lm) {
map<int, int> m, dm, um;
m[0] = 1;
dm[0] = 1;
um[0] = 1;
vector<pair<ll, pll>> T;
for(int j = 0; j < n; j++) {
T.pb(MP(R - v[j].F, MP(0, 0)));
}
for(int i = 0; i < n; i++) {
if(Dr[i] != -1 && Dl[i] > lm) {
dm[C - v[i].S]++;
if(Dl[i] == Dr[i] && Dr[i] != INF)
T.pb(MP(Dr[i] - lm, MP(1, C - v[i].S)));
else if(Dr[i] != INF)
T.pb(MP(Dr[i], MP(1, C - v[i].S)));
}
if(Ur[i] != -1 && Ul[i] > lm) {
um[v[i].S - 1]++;
if(Ul[i] == Ur[i] && Ur[i] != INF)
T.pb(MP(Ur[i] - lm, MP(2, v[i].S - 1)));
else if(Ur[i] != INF)
T.pb(MP(Ur[i], MP(2, v[i].S - 1)));
}
for(int j = i + 1; j < n; j++) {
if(L_lim[i][j] <= lm) continue;
if(dis[i][j] <= 0) continue;
T.pb(MP(L[i][j] - lm, MP(0, dis[i][j])));
if(L_lim[i][j] == R_lim[i][j] && R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j] - lm, MP(0, -dis[i][j])));
else if(R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j], MP(0, -dis[i][j])));
}
}
sort(ALL(T));
// cout << lm << '\n';
// for(auto i : T) cout << i.S.F << ' ' << i.F << ' ' << i.S.S << '\n';
int flag = 0, top = 0;
while(top < (int)T.size()) {
if(flag || T[top].F <= R - rest) {
do {
if(T[top].S.F == 0) {
if(T[top].S.S < 0) {
m[-T[top].S.S]--;
} else if(T[top].S.S > 0) {
m[T[top].S.S]++;
}
} else if(T[top].S.F == 1) {
dm[T[top].S.S]--;
} else {
um[T[top].S.S]--;
}
top++;
} while(top < (int)T.size() && T[top].F == T[top - 1].F);
}
flag = 1;
while(m.rbegin() -> S == 0) {
auto p = m.end(); p--;
m.erase(p);
}
while(dm.rbegin() -> S == 0) {
auto p = dm.end(); p--;
dm.erase(p);
}
while(um.rbegin() -> S == 0) {
auto p = um.end(); p--;
um.erase(p);
}
ll rm = 0;
if(top - 1 >= 0)
rm = max(rm, T[top - 1].F);
// cout << lm << ' ' << rm << ' ' << m.rbegin() -> F << ' ' << dm.rbegin() -> F << ' ' << um.rbegin() -> F << '\n';
if(lm + rm >= minm) {
ll tans = lm + rm + max(m.rbegin() -> F, dm.rbegin() -> F + um.rbegin() -> F);
ans = min(ans, tans);
}
}
}
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
580 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
580 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
