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

0. 前言

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

1. 题意解释

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

2. 初步思考

不难发现，正如其他题解所说，只需要把所有的交点的

y

坐标存下来就可以了，不妨存在

y

数组，其中

y

数组按照升序排列。

则计算

\sum\limits_{i=1}^{\frac{n}{2}} y_{2i}-y_{2i-1}

即可

3. 细节考虑

楼下没有说清楚的有：

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

不难发现，对于每一个

x = sx

的点，都是特殊的。

考虑这一个点的上一个点和下一个点，

如果在同侧，则这个点是无用的点。

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

注意到：

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

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

4, 代码

那么代码就很简单了。

code

CPP

#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。

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

文章操作

0. 前言

1. 题意解释

2. 初步思考

3. 细节考虑

4, 代码

相关推荐

评论

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