蓝桥杯2015年第六届真题-广场舞-题解（C++代码）

537 阅读 2 评论 0 点赞

原题链接：蓝桥杯2015年第六届真题-广场舞

#### 跟上面的优质题解用的好像是同样的算法，但是他没提及PNPOLY算法，直接看可能很迷
#### 代码留存，用到了PNPoly算法判断一个点在不在多边形内
#####PNPoly算法代码：
```cpp
bool f(int x, int y) {
	bool f = false;
	for (int i = 0, j = n - 1; i < n; j = i++) {
		if ( ((y < ny[i]) != (y < ny[j])) &&
		(x > (1.0 * nx[j] - nx[i]) * (1.0 * y - ny[i]) / (1.0 * ny[j] - ny[i]) + nx[i]) ) {
			f = !f;
		}
	}
	return f;
}
```
算法讲解：https://www.cnblogs.com/anningwang/p/7581545.html
（大致看了一下，感觉他这里面给的代码是错误的，自己推了一遍，上面是自己写的）

```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int nx[N], ny[N];
int n;
int maxx = -N, minx = N, maxy = -N, miny = N;
int ans = 0;
bool f(int x, int y) {
	bool f = false;
	for (int i = 0, j = n - 1; i < n; j = i++) {
		if ( ((y < ny[i]) != (y < ny[j])) &&
		(x > (1.0 * nx[j] - nx[i]) * (1.0 * y - ny[i]) / (1.0 * ny[j] - ny[i]) + nx[i]) ) {
			f = !f;
		}
	}
	return f;
}
bool is(int x, int y) {
	return f(x + 1, y) && f(x, y + 1) && f(x + 1, y + 1) && f(x, y);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nx[i] >> ny[i];
		maxx = max(nx[i], maxx);
		minx = min(nx[i], minx);
		maxy = max(ny[i], maxy);
		miny = min(ny[i], miny);
	}
	for (int i = minx; i < maxx; i++) {
		for (int j = miny; j < maxy; j++) {
			if (is(i, j)) {
				ans ++;
			}
		}
	}
	cout << ans;
	return 0;
}
```

0.0分

2 人评分

本文分类：题解列表
浏览次数：537 次浏览
发布日期：2020-11-12 17:22:39
本文链接：https://blog.dotcpp.com/a/73735

上一篇 > [编程入门]迭代法求平方根-题解（C语言代码）
下一篇 > [编程入门]自定义函数处理素数-题解（C语言代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2015年第六届真题-广场舞-题解（C++代码）

评论列表共有 2 条评论

发表评论取消回复

蓝桥杯2015年第六届真题-广场舞-题解（C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 2 条评论

发表评论 取消回复

评论列表共有 2 条评论

发表评论取消回复