#include <bits/stdc++.h>
using namespace std;
#define int long long
main() {
int n, x0, y0;
cin >> x0 >> y0 >> n;
int a[n], b[n];
for(int i=0;i<n;i++)
cin >> a[i] >> b[i];
vector<int> xminus = {0}, yminus = {0}, xplus = {0}, yplus = {0};
for(int i=0;i<n;i++) {
xminus.push_back(a[i]-1);
xplus.push_back(x0-a[i]);
yminus.push_back(b[i]-1);
yplus.push_back(y0-b[i]);
}
long long ans = 4e12;
for(auto west: xminus)
for(auto east: xplus) {
vector<int> spec = {1, x0};
for(int i=0;i<n;i++) {
spec.push_back(max(1LL,a[i]-west));
spec.push_back(min(x0,a[i]+east)+1);
}
sort(spec.begin(),spec.end());
spec.resize(unique(spec.begin(),spec.end())-spec.begin());
if(spec.back() == x0 + 1)
spec.pop_back();
int impt = spec.size();
vector<int> pts[impt];
for(int i=0;i<n;i++) {
for(int j=0;j<impt;j++)
if(a[i]-west <= spec[j] && spec[j] <= a[i]+east)
pts[j].push_back(b[i]);
}
int minTot = 0, minNorth = 0, minSouth = 0;
for(int i=0;i<impt;i++) {
sort(pts[i].begin(),pts[i].end());
int sz = pts[i].size();
if(sz == 0) {
minTot = 2e12;
break;
}
for(int j=0;j<sz-1;j++)
minTot = max(minTot,pts[i][j+1]-pts[i][j]-1);
minNorth = max(minNorth,y0-pts[i][sz-1]);
minSouth=max(minSouth,pts[i][0]-1);
}
ans = min(ans, 0LL + max(minTot,minNorth+minSouth) + west + east);
}
for(auto south: yminus)
for(auto north: yplus) {
vector<int> spec = {1, y0};
for(int i=0;i<n;i++) {
spec.push_back(max(1LL,b[i]-south));
spec.push_back(min(y0,b[i]+north)+1);
}
sort(spec.begin(),spec.end());
spec.resize(unique(spec.begin(),spec.end())-spec.begin());
if(spec.back() == y0 + 1)
spec.pop_back();
int impt = spec.size();
vector<int> pts[impt];
for(int i=0;i<n;i++) {
for(int j=0;j<impt;j++)
if(b[i]-south <= spec[j] && spec[j] <= b[i]+north)
pts[j].push_back(b[i]);
}
int minTot = 0, minEast = 0, minWest = 0;
for(int i=0;i<impt;i++) {
sort(pts[i].begin(),pts[i].end());
int sz = pts[i].size();
if(sz == 0) {
minTot = 2e12;
break;
}
for(int j=0;j<sz-1;j++)
minTot = max(minTot,pts[i][j+1]-pts[i][j]-1);
minEast = max(minEast,x0-pts[i][sz-1]);
minWest=max(minWest,pts[i][0]-1);
}
ans = min(ans, 0LL + max(minTot,minEast+minWest) + south + north);
}
if(int x1=0;1)
if(int y1=0;1) {
vector<int> specX = {x0+x1}, specY = {y0+y1};
for(int i=0;i<n;i++) {
if(a[i]-x1-1 >= 1)
specX.push_back(a[i]-1);
if(b[i]-y1-1 >= 1)
specY.push_back(b[i]-1);
}
vector<pair<int,int>> cond;
for(auto xs: specX)
for(auto ys: specY) {
pair<int,int> pts[n];
for(int i=0;i<n;i++) {
if(a[i] <= xs && b[i] <= ys)
pts[i] = {xs-a[i],ys-b[i]};
else
pts[i]={2e12,2e12};
}
sort(pts,pts+n);
int pmin = 2e12;
cond.push_back({pts[0].first,2e12});
for(int i=0;i<n;i++) {
pmin = min(pmin, pts[i].second);
cond.push_back({(i==n-1?2e12:pts[i+1].first),pmin});
}
}
cond.push_back({2e12,y1});
cond.push_back({x1,2e12});
sort(cond.begin(),cond.end());
int sz = cond.size();
for(int i=sz-1;i--;)
cond[i].second = max(cond[i].second, cond[i+1].second);
for(int i=1;i<sz;i++)
ans = min(ans, 0LL+cond[i-1].first+cond[i].second);
}
cout << ans;
}
Compilation message (stderr)
cultivation.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
4 | main() {
| ^~~~
# | 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... |