丘比特的箭（点是否在面内）- HDU 1756

（红心点为A，右边有3个点，说明在多边形内部）

（向量的乘积）

a·b>0 方向基本相同，夹角在0°到90°之间

a·b=0 正交，相互垂直

a·b<0 方向基本相反，夹角在90°到180°之间

（P1A的斜率大于P1P2的斜率）

Problem Description

Input

Output

Sample Input

4

10 10

20 10

20 5

10 5

2

15 8

25 8

Sample Output

Yes

No

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const double eps = 1e-6;

struct Point {
double x, y;
Point(double x = 0, double y = 0): x(x), y(y) {}

//向量+
Point operator +(const Point &b)const
{
return Point(x + b.x, y + b.y);
}

//向量-
Point operator -(const Point &b)const
{
return Point(x - b.x, y - b.y);
}

//点积
double operator *(const Point &b)const
{
return x * b.x + y * b.y;
}

//叉积
double operator ^(const Point &b)const
{
return x * b.y - b.x * y;
}
};

static Point polygons[105];

//三态函数，判断两个double在eps精度下的大小关系
int dcmp(double x)
{
if (fabs(x) < eps) return 0;
else
return x < 0 ? -1 : 1;
}

//判断点Q是否在P1和P2的线段上
bool is_in_line(Point P1, Point P2, Point Q)
{
return dcmp((P1 - Q) ^ (P2 - Q)) == 0 && dcmp((P1 - Q) * (P2 - Q)) <= 0;
}

//判断点P在多边形内-射线法
bool is_in_polygon(Point P, int point_count)
{
bool flag = false;

for (int i = 1, j = point_count; i <= point_count; j = i++)
{
//多边形一条边的两个顶点
Point P1 = polygons[i];
Point P2 = polygons[j];

//点在多边形一条边上
if (is_in_line(P1, P2, P)) {
return true;
}
//在多边形里面
//以P点做一条水平向右的射线

//1、线段在点的上下，而不是一边
bool isUpDownLine = (dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0);

if (isUpDownLine) {
//2、点在射线与线段交点的左边
//直线应该是y=kx+b吧
//假如当前点是坐标是x1,y1，那么y>kx+b就说明点在直线左边，反之在右边
/*
p.x < (p.y-p1.y)/k + p1.x
k*p.x < p.y-p1.y + k*p1.x
p.y-p1.y + k*(p1.x-p.x) > 0
p.y-p1.y > k*(p.x-p1.x)
对于如果向量P1P的斜率大于P1P2的斜率，则P在P1P2的左边
*/
bool isLeft = dcmp(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0;

if (isLeft) {
flag = !flag;
}
}
}

return flag;
}

int main()
{
int case_count, point_count;

while (~scanf("%d", &point_count))
{
for (int i = 1; i <= point_count; i++) {
scanf("%lf %lf", &polygons[i].x, &polygons[i].y);
}

Point point;
scanf("%d", &case_count);

while (case_count--)
{
scanf("%lf %lf", &point.x, &point.y);
//判断是否在多边形里面
if (is_in_polygon(point, point_count)) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
}
return 0;
}```

0 条评论

• 随机增量算法 - 最小圆覆盖

随机增量算法是计算几何的一个重要算法，它对理论知识要求不高，算法时间复杂度低，应用范围广大。

• leetcode 题解 | 121. 买卖股票的最佳时机

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

• leetcode 50 | 实现pow函数

就比如3的4次方，其实是3的平方乘以3的平方，依据算式3，那么就能写出递归的写法，注意如果n为奇数，n/2取整对丢失1，则有：

• 03 . MysSQL权限和备份

恢复时间点之前首先将全量备份恢复之后，在此基础上回放增加的binlog直至指定的时间点

• 创建你的第一个shell脚本

安装自己的虚拟机或者买个什么云服务，有的也是很便宜。我之前买的一个云三年300多。

• 最佳实践 | 3个服务营销实例，教你轻松实现“增长”

? ? “增长”是近年来众多大小企业都面临的核心痛点，如何高效增长？如何持续增长？大家都在探索数字化时代的“增长”之道。 在实际业务环节中，客户触达、获客转...

• 视频配音篇，如何使用百度翻译将文本转换为mp3语音？

这里推荐使用Chrome浏览器，当然新版Edge也更换了Chrome内核，操作方式基本相同；

• 聊聊spring-data-redis的连接池的校验

spring-data-redis/2.0.10.RELEASE/spring-data-redis-2.0.10.RELEASE-sources.jar!/o...

• 聊聊debezium的ChangeEventQueue

debezium-v1.1.1.Final/debezium-core/src/main/java/io/debezium/connector/base/Cha...

• 聊聊debezium的ChangeEventQueue

debezium-v1.1.1.Final/debezium-core/src/main/java/io/debezium/connector/base/Cha...