题解：P11104 [ROI 2023] 监控 (Day 1)

chenyizhen · 2025-06-01 10:30:49 · 题解

思路：

仔细分析，很明显我们横向移动和纵向移动是互不影响的，那么我们就可以把横向和纵向分开来分析，这种将互不相干的几个量分离开的思想不仅在奥赛中，在文化课中也有广泛应用。

注意

• 在找 cnt_h 和 cnt_w 时，我们是通过对比当前点距边缘最小值与当前最小值。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5;
inline void read(int &a){
    char ch;int f=1,k=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    a=k*f;
}
int h,w,k,min_h,min_w,cnt_h,cnt_w;
int x[N],y[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    read(h),read(w),read(k);
    for(int i=1;i<=k;i++)
        read(x[i]),read(y[i]);

    sort(x+1,x+1+k);sort(y+1,y+1+k);
    min_h=x[k]-x[1]+1;min_w=y[k]-y[1]+1;

    for(int i=1;i<k;i++){
        if(h-(x[i+1]-x[i])+1<min_h){
            min_h=h-(x[i+1]-x[i])+1;
            cnt_h=min(min(x[i],h-x[i]),min(x[i+1],h-x[i+1]+1));
        }else if(h-(x[i+1]-x[i])+1==min_h)
            cnt_h=min(cnt_h,min(min(x[i],h-x[i]),min(x[i+1],h-x[i+1]+1)));

        if(w-(y[i+1]-y[i])+1<min_w){
            min_w=w-(y[i+1]-y[i])+1;
            cnt_w=min(min(y[i],w-y[i]),min(y[i+1],w-y[i+1]+1));
        }else if(w-(y[i+1]-y[i])+1==min_w)
            cnt_w=min(cnt_w,min(min(y[i],w-y[i]),min(y[i+1],w-y[i+1]+1)));
    }
    cout<<min_h*min_w<<' '<<cnt_h+cnt_w;
    return 0;
}