题解 P1663 【山】

· · 题解

二分+思维的一道妙题。

需要些许数学知识和一个有点空间意识的脑子。

题意简述:

平面直角坐标系上N个点相连形成一条折线。
要求找到Y值最小的一个点。
使得它位于每一段折线所在的直线的上方。

思路历程：

考虑平面直角坐标系上的整条折线如下图：

而把“每一段折线所在的直线”补起来就像这样：

\qquad \mathcal{Task\ 1.} 什么样的点才满足题目要求？

我们要取的是”每一段折线所在直线“的上方的点。

由于每一段折线的起点与终点是明确已知的，所以他的“上半部分”必然也是已知的。

而我们选取的点，则需要位于每一段折线的“上半部分”，所以便是要取所有“上半部分”的交。

看图我们便可知道，必定存在且只存在一个 Y 值最小的点，使它在每一段折线的“上半部分”。

这个最小的 Y 具象到图像上，就是所有“包含阴影部分的水平直线”中最低的一条。

\qquad \mathcal{Task\ 2.} 如何查一条水平直线是否包含阴影部分？

『阴影部分必然是一个联通的多边形。』

原因显然，在同一条水平直线上，不可能存在一个点，一开始在一条直线上方，突然就不在了，突然又到了他的上方的情况（这可是一次函数）。

所以对于一条水平直线，他上面的阴影部分要么没有，要有就是一个固定的区间。

既然阴影部分在一条水平直线上，只存在一个区间。那这个阴影区间我们便可以通过每一段折线的斜率信息，来限定在一个明确的范围里。

\qquad \mathcal{Task\ 3.} 怎么限定阴影部分的范围？

具体地说，限定方法如下：

不妨画图理解。我们现在暂定下 Y= 0.3

黄线的 Y=0.5 我们现在的 0.3 低于其，故必不存在阴影部分。

此时需要我们改变 Y 值。

此时蓝线的斜率小于0，故阴影部分的区间被限制在 \{ x|x\geq 0.1 \} 范围内。

此时粉线的斜率大于0，故阴影部分的区间被限制在 \{ x|0.1\leq x\leq 5.6 \} 范围内。

这时我们就有了一个明确的区间了。而一条水平直线上，阴影区间存在，也就是代表包含了阴影部分，它的条件显然是 右边界大于左边界 。

那这道题就可以轻松解决了，我们只需二分找到最小的，使阴影区间存在的Y 值即可。

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5007;
const double INF = 2e9;

struct line//代表一条直线
{
    double k, b;
    //斜率与截距
} l[MAX];

int N;
double x[MAX], y[MAX];
//存点的 x,y 坐标
double L, R;//左、右边界
double ans;//答案（指最低的Y值）

bool judge(double Y)//获取阴影区间
{
    L = -INF, R = INF;
    for (int i = 1; i <= N; i++)
    {
        if (l[i].k < 0)//截距<0，更新左边界
        {
            L = max(L, (Y - l[i].b) / l[i].k);
        }
        if (l[i].k > 0)//截距>0，更新右边界
        {
            R = min(R, (Y - l[i].b) / l[i].k);
        }
        if (l[i].k == 0)
        {
            if (l[i].b > Y)//截距=0，若低于这条线，则必不存在阴影区间
            {
                return 0;
            }
        }
    }
    return R - L >= 1e-8;//返回右区间是否大于左区间
}
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> x[i] >> y[i];//输入
    }
    N--;
    for (int i = 1; i <= N; i++)//算出来斜率与截距
    {
        l[i].k = (1.0) * (y[i] - y[i + 1]) / (x[i] - x[i + 1]);
        l[i].b = (1.0) * y[i] - x[i] * l[i].k;
    }
    double l = 0, r = INF;
    while (r - l >= 1e-8)//二分查找最小Y值
    {
        double mid = (l + r) / 2.0;
        if (judge(mid))
        {
            ans = mid;
            r = mid;
            //不能是mid-1，因为Y是小数，不敢说(mid-1)~mid 之间没有答案
        }
        else
        {
            l = mid;
        }
    }
    printf("%.2lf\n", ans);
}