This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N=305;
const int INF=2e9;
int n;
int r,c;
int x[N],y[N];
int gx,gy;
int calc(int dx){
vector<int> xs;
for(int i=0;i<n;i++){
if(x[i]+dx<gx)return INF;
xs.emplace_back(max(x[i],gx));
xs.emplace_back(min(x[i]+dx,gx+r-1)+1);
}
xs.emplace_back(gx);
xs.emplace_back(gx+r);
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
int xn=xs.size();
vector<vector<pair<int,int>>> event(xn);
for(int i=0;i<n;i++){
int xi=lower_bound(xs.begin(),xs.end(),max(x[i],gx))-xs.begin();
int xj=lower_bound(xs.begin(),xs.end(),min(x[i]+dx,gx+r-1)+1)-xs.begin();
assert(xi<xj);
event[xi].emplace_back(y[i],1);
event[xj].emplace_back(y[i],0);
}
event.pop_back();
int mxa=0,mxb=0,sum=0;
multiset<int> pts,dif;
for(auto &e:event){
for(auto [x,t]:e){
if(t){
auto it=pts.emplace(x);
if(next(it)!=pts.end()&&it!=pts.begin()){
dif.erase(dif.find(*next(it)-*prev(it)));
}
if(next(it)!=pts.end()){
dif.emplace(*next(it)-*it);
}
if(it!=pts.begin()){
dif.emplace(*it-*prev(it));
}
}else{
auto it=pts.find(x);
assert(it!=pts.end());
if(next(it)!=pts.end()){
dif.erase(dif.find(*next(it)-*it));
}
if(it!=pts.begin()){
dif.erase(dif.find(*it-*prev(it)));
}
if(next(it)!=pts.end()&&it!=pts.begin()){
dif.emplace(*next(it)-*prev(it));
}
pts.erase(it);
}
}
if(pts.empty())return INF;
mxa=max(mxa,*pts.begin()-gy);
mxb=max(mxb,gy+c-1-*pts.rbegin());
if(!dif.empty()){
sum=max(sum,*dif.rbegin()-1);
}
}
return min(INF,dx+max(sum,mxa+mxb));
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> r >> c >> n;
for(int i=0;i<n;i++){
cin >> x[i] >> y[i];
}
pair<int,int> px(INF,INF),py(INF,INF);
for(int i=0;i<n;i++){
px=min(px,{x[i],y[i]});
py=min(py,{y[i],x[i]});
}
gx=py.second;
gy=px.second;
vector<int> xs;
for(int i=0;i<n;i++){
xs.emplace_back(x[i]-1);
xs.emplace_back(r-x[i]);
for(int j=0;j<n;j++){
int d=abs(x[i]-x[j]);
xs.emplace_back(d);
if(d>0){
xs.emplace_back(d-1);
}
}
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
int ans=r+c-2;
for(int dx:xs){
ans=min(ans,calc(dx));
}
cout << ans;
}
# | 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... |