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:

CPP

#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;
}

完结撒花！！！

P12623 [ICPC 2025 NAC] Geometry Rush 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

P12623 [ICPC 2025 NAC] Geometry Rush 题解