丘比特的箭（点是否在面内）- HDU 1756
对于点A是否在多边形P内的判定， 一般有两种方法：射线法和转角法。 这里介绍一下射线法。
射线法：从点A出发作一条射线，计算这条射线与多边形P的边的交点数量N，如果N为奇数，则点A在多边形P内，否则在P外部。
射线法中这条射线是任意方向的，一般在编程的时候选取从A出发往X坐标轴正方向的一条射线X。
（红心点为A，右边有3个点，说明在多边形内部）
射线法的原理：直线不可能从内部再次进入多边形，或从外部再次穿出多边形，即连续两次穿越边界的情况必然成对（大概就是这个意思，不是严格证明）。
射线法具体逻辑见源代码，涉及到几个子问题，大概说一下。
子问题1：判定点A在线段P1P2上（特殊处理点在边上的情况使用）。
两个向量a和b的叉积写作a^b = |a| |b|sinα （α为a，b向量之间的夹角）
叉积的几何意义：
对于向量AP1与向量AP2，如果叉积为0，说明夹角为0，也就是共线。
另外还要注意向量a、b的乘积a·b。
（向量的乘积）
乘积的几何意义：
a·b>0 方向基本相同，夹角在0°到90°之间
a·b=0 正交，相互垂直
a·b<0 方向基本相反，夹角在90°到180°之间
子问题2：判断点A在线段P1P2的左边。
对于线段P1P2的斜率k，如果P1A的斜率k'大于k，则A在线段P1P2的左边。
（P1A的斜率大于P1P2的斜率）
Problem Description
传说世上有一支丘比特的箭，凡是被这支箭射到的人，就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想，在得到这支箭前，他总得先学会射箭。
日子一天天地过，Lele的箭术也越来越强，渐渐得，他不再满足于去射那圆形的靶子，他开始设计各种各样多边形的靶子。
不过，这样又出现了新的问题，由于长时间地练习射箭，Lele的视力已经高度近视，他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers，你能帮帮他嘛？
Input
本题目包含多组测试，请处理到文件结束。
在每组测试的第一行，包含一个正整数N(2<N<100),表示靶子的顶点数。
接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。
然后有一个正整数M，表示Lele射的箭的数目。
接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。
Output
对于每枝箭，如果Lele射中了靶子，就在一行里面输出"Yes",否则输出"No"。
Sample Input
4
10 10
20 10
20 5
10 5
2
15 8
25 8
Sample Output
Yes
No
源代码：G++ 0ms
#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;
}腾讯云开发者
