题解：P3738 [HAOI2014] 穿越封锁线

· · 题解

0. 前言

前情提要（1）

前情提要（2）

这道题目终于有可以通过所有样例并且可以通过所有数据的题解啦。

1. 题意解释

从一个点出发，从这个地方往上走，被一个多边形覆盖的长度。

2. 初步思考

不难发现，正如其他题解所说，只需要把所有的交点的 y 坐标存下来就可以了，不妨存在 y 数组中，其中 y 数组按照升序排列。

则计算 \sum\limits_{i=1}^{\frac{n}{2}} y_{2i}-y_{2i-1} 即可。

3. 细节考虑

楼下没有说清楚的有：

  1. 其实是从 (sx, sy) 开始的，所以要考虑低于 sy 的部分。
  2. 这里对于竖直的边的处理。

不难发现，对于每一个 x = sx 的点，都是特殊的。

考虑这一个点的上一个点和下一个点，如果在同侧，则这个点是无用的点。

但是这样还是不够全面，没有考虑竖线的情况。

注意到：

  1. 如果上一个点到这一个点的连线是直线，那么只有下一个点的 x 坐标大于 sx（当前点的 x 坐标）时，这个点才有用。
  2. 如果下一个点到这一个点的连线是直线，那么只有上一个点的 x 坐标大于 sx（当前点的 x 坐标）时，这个点才有用。

此处比较抽象，很抱歉没有给出图片，但是留作读者作业（偷笑）。

4. 代码

那么代码就很简单了。

:::success[code]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;

int n;
double y[N], sx, sy;
bool jd[N];

struct point{
    double x, y;
} a[N];

double get_y(point a, point b, double x){
    double _1 = b.x - a.x, _2 = x - a.x;
    double _3 = b.y - a.y, _4 = _3 / _1 * _2;
    return a.y + _4;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i].x >> a[i].y;
    cin >> sx >> sy;

    for (int i = 1; i <= n; i ++ ){
        if (a[i].x != sx) continue;
        int pre = (i == 1 ? n : i - 1);
        int nxt = (i == n ? 1 : i + 1);
        if ((a[pre].x <= sx && a[nxt].x <= sx) || (a[pre].x >= sx && a[nxt].x >= sx)) jd[i] = true;
        if (a[pre].x == sx && a[nxt].x > sx) jd[i] ^= 1;
        if (a[nxt].x == sx && a[pre].x > sx) jd[i] ^= 1;
    }

    int m = 0;
    for (int i = 1; i <= n; i ++ ){
        int j = i % n + 1;
        if (a[i].x == sx){
            if (!jd[i]) y[++ m] = a[i].y;
        }
        if (a[i].x == a[j].x) continue;
        if ((a[i].x < sx && sx < a[j].x) || (a[j].x < sx && sx < a[i].x)) y[++ m] = get_y(a[i], a[j], sx);
    }

    sort(y + 1, y + m + 1);

    int j = 1;
    while (j <= m && y[j] < sy) j ++;

    if (j > m){
        cout << "0\n";
        return 0;
    }

    double ans = 0;
    if (j % 2 == 0) ans += y[j] - sy, j ++ ;

    while (j <= m){
        ans += y[j + 1] - y[j];
        j += 2;
    }

    cout << (int)ans << "\n";
    // cout << fixed << setprecision(0) << ans << "\n";
}

:::

如果有帮助就给个赞吧 qwq。