lw

用户名：saudade

访问量：12586

签　名：

等　　级
排　　名	175
经　　验	6717
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

得得得得得
浏览：219

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

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

　　作者: lw　　　　发表时间：2020-11-12 17:22:39 浏览：323　|　评论：2　

原题链接：蓝桥杯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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

shiren

nb了，x > (1.0 * nx[j] - nx[i]) * (1.0 * y - ny[i]) / (1.0 * ny[j] - ny[i]) + nx[i]；这简单的一句结合图形来看，就实现了射线法。。。666
实际上是一条以待测点为终点的射线（y=text_y），然后，看他穿过了多少条边；

2021-04-12 20:54:27

flags

坐标问题  你们都没错

2021-04-05 15:36:21

lw

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

地宫取宝（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

整除问题（C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

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

评论区

精彩推荐

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-进制转换（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

WU-输入输出格式练习（C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

用筛法求之N内的素数。（C语言代码）

1128题解（返回值为数组的情况）

C二级辅导-计负均正（C语言代码）

陈教主的三角形（C语言代码）

lw

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

地宫取宝 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C++代码）

整除问题 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

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

评论区

精彩推荐

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-进制转换 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

WU-输入输出格式练习 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

用筛法求之N内的素数。 （C语言代码）

1128题解（返回值为数组的情况）

C二级辅导-计负均正 （C语言代码）

陈教主的三角形 （C语言代码）

地宫取宝（C语言代码）

整除问题（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

WU-输入输出格式练习（C++代码）

用筛法求之N内的素数。（C语言代码）

C二级辅导-计负均正（C语言代码）

陈教主的三角形（C语言代码）