【题解】P1663-山

_Yoimiya_ · 2021-04-17 19:46:57 · 题解

本题前置知识 :

1. 斜率 ( Slope ) ：当直线L的斜率存在时，对于一次函数 y = kx + b （斜截式），k即该函数图像的斜率。
2. 二分答案（这应该不用说吧，来做蓝题的人应该都会）

题意

给出n个点相连形成一条折线。
要求找到一个点使得它位于每一段线段的上方且y值最小。

如何理解在每一条线段上方呢？

思路

• 先转换问题，考虑求2条线段的上方，则符合条件的点都在2条直线上方，也就是处于线段交的上方，此时显然符合条件的点是两条线段的交点。
• 问题来了，要解决这个题目，首先要求出什么点在直线上方。那么怎么确定点是否在直线上方呢？
• 首先，我们先求出点 (x_n,y_n) 和点 (x_{n-1},y_{n-1})的解析式。（公式如下：设 l :y = kx + b , 则 k = \frac{y_n-y_{n-1}}{x_n - x_{n-1}} b = y_n - kx_n
• 而后通过二分答案来枚举每个直线 y = mid （题目只要求求最小的 y 值） ,判断符不符合条件:
  1.斜率 k=0 : 判断该直线的 b 是否小于 mid ;
  2.斜率 k>0 ：取该直线与直线 y = mid 的交点，保存最小值（符合条件的最左端） 3.斜率 k<0: 取该直线与直线 y = mid 的交点，保存最大值（符合条件的最右端）
• 判断在 k < 0 符合条件的最大值是否小于在 k > 0符合条件的最小值,不是则标志着这个点不满足在所有线段上方，排除，返回 false。
• 输出，保留2位小数。

代码

#include<bits/stdc++.h>
using namespace std;
const int M(5e3+1);
int n;
double x[M],y[M],slope[M],b[M],ans;
inline bool check(double x){
    double L(-2e9),R(2e9);
    for(register int i(2);i<=n;++i)
    {
        if(slope[i]<0) L=max(L,(x-b[i])/slope[i]);
        else{
            if(slope[i]>0) R=min(R,(x-b[i])/slope[i]);
            else if(x<b[i]) return 0;
        }
    }
    return L<=R;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(register int i(1);i<=n;++i){
        cin>>x[i]>>y[i];
        slope[i]=(y[i]-y[i-1])/(x[i]-x[i-1]);
        b[i]=y[i]-slope[i]*x[i];
    }
    register double l(0),r(2e9+1);
    while(l<=r){
        double mid=(l+r)/2;
        if(check(mid))r=mid-0.0001,ans=mid;
        else l=mid+0.0001;
    }
    printf("%.2lf",ans);
    return 0;
}

补充说明

• check 函数里从2开始是因为第一个点没有左边的线段。
• 2e9 是之前 WA 了，调代码时以为是范围不够大开的。