P12623 [ICPC 2025 NAC] Geometry Rush 题解

· · 题解

思路分析：

这有蓝吗？ 小清新蓝题。

假设我们知道了每个点的上下界，那么我们只需要模拟两个点——最低点和最高点的行动就可以知道合法的范围。具体的，先贪心的把最高点向上走一步，最低点向下走一步，如果超出限定范围直接取到限定范围内。特别的是，我们需要保证当前坐标 (x,y) 满足 x+y\bmod 2 为 0，因为不管向右上还是右下走都不改变 x+y 的奇偶性。如果过程中任意时刻最低点高于最高点，就无解。

接下来就是如何处理每个点的上下界。题目保证给出的节点是从左到右的，那直接暴力维护即可。具体的，如果 x_{i-1}<x_i 那么，直接求出直线方程，代入 (x_{i-1},x_i) 内的每个点。

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int n,m,w,h,x[N],y[N],l[N],r[N];
signed main(){
    cin>>n>>m>>w>>h;
    for(int i=0;i<=w;i++)
        r[i]=h,l[i]=-h;
    cin>>x[0]>>y[0];
    for(int i=1;i<n;i++){
        cin>>x[i]>>y[i];
        r[x[i]]=min(r[x[i]],y[i]);
        if(x[i]!=x[i-1]){
            double K=(y[i]-y[i-1])*1.0/(x[i]-x[i-1]);
            double B=y[i]-K*x[i];
            for(int j=x[i-1]+1;j<x[i];j++)
                r[j]=ceil(K*j+B);
        }
    }
    cin>>x[0]>>y[0];
    for(int i=1;i<m;i++){
        cin>>x[i]>>y[i];
        l[x[i]]=max(l[x[i]],y[i]);
        if(x[i]!=x[i-1]){
            double K=(y[i]-y[i-1])*1.0/(x[i]-x[i-1]);
            double B=y[i]-K*x[i];
            for(int j=x[i-1]+1;j<x[i];j++)
                l[j]=floor(K*j+B);
        }
    }
    int mn=0,mx=0;
    for(int i=1;i<=w;i++){
        mn=max(--mn,l[i]+1);
        if((mn+i)%2!=0)mn++;
        mx=min(++mx,r[i]-1);
        if((mx+i)%2!=0)mx--;
        if(mn>mx)return cout<<"impossible",0;
    }
    cout<<mn<<' '<<mx;
    return 0;
}

完结撒花！！！