题解：P14632 [2018 KAIST RUN Fall] Rising Sun

hlb44 · 2025-12-03 13:45:22 · 题解

我们按照以下步骤实现：

算边界关键点坐标

设坐标为 (a_i, y_i)，其中 a_i 为输入的 x 坐标序列。

• 若x = a_i，则 h = y_i；
• 若 x 在区间 [a_i, a_{i+1}] 内：i 为偶数，h = y_i + (x - a_i)，否则 h = y_i - (x - a_i)。

推临界高度 t

山区内部不与该线段相交的条件是：对所有 x' < x 的边界点 (a_i, y_i)，满足 y_i \le \frac{h - t}{x}a_i + t。

整理得：t \ge \frac{x \cdot y_i - h \cdot a_i}{x - a_i}。

只需找最大 t 值即可。

算最后答案

• 若最大 t 值是 \le 0 的，答案为 0；
• 否则，对最大 t 值向上取整。

交叉相乘不做解释。

代码实现（C++）

#include<bits/stdc++.h>
#define fo(i,begin,end) for(int i=begin;i<=end;i++)
#define ll long long
using namespace std;
ll a[2005],y[2005],hx,hy,ans;
int n,m,k;
double maxT=-1e18;
int main() {
    cin>>n,m=2*n;
    fo(i,1,m) cin>>a[i];
    cin>>hx;
    // 计算边界每个关键点的y坐标
    fo(i,2,m) {
        if((i-1)%2==1)y[i]=y[i-1]+(a[i]-a[i-1]);
        else y[i]=y[i-1]-(a[i]-a[i-1]);
    }
    // 定位家所在的边界线段区间
    fo(i,1,m-1) if(a[i]<=hx&&hx<=a[i+1]) {k=i;break;}
    // 计算家的y坐标hy
    hy=(k%2)?(y[k]+hx-a[k]):(y[k]-(hx-a[k]));
    fo(i,1,k) {
        ll xp=a[i];// 边界点的x坐标
        if(xp==hx) continue;// 重合点无遮挡，跳过
        double b=y[i],ch=b*hx-hy*xp,fa=hx-xp,f=ch/fa;
        //边点y坐标   分子          分母     分数值 
        if(f>maxT) maxT=f;
    }
    if(maxT>0) ans=ceil(maxT);
    cout<<ans;
    return 0;
}