几何-判断点在凸多边形内部

题目链接:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1429

题目

凸多边形
Time Limit: 2000 MS
Memory Limit: 65536 K
Total Submit: 445(90 users)
Total Accepted: 130(73 users)
Special Judge: No
Description
已知一个凸多边形A(包含n个点,点按照顺时针给出),和一个点集B(包含m个点),请判断这m个点是否都严格在凸多边形A内部。
Input
输入包含多组测试数据。对于每组测试数据:第1行,包含一个整数n (3 ≤ n ≤ 1e5)代表着凸多边形A的点的数量。接下来n行每行包含一个坐标(x, y) (-1e9 ≤ x, y ≤ 1e9) 表示这个凸多边形,点按照顺时针给出。第n + 2行,包含一个整数m (3 ≤ m ≤ 1e5)代表着点集B的点的数量。接下来m行每行包含一个坐标(x, y) (-1e9 ≤ x, y ≤ 1e9) 表示这个点集B。处理到文件结束
Output
对于每组测试数据:第1行,如果点集B都严格在凸多边形A内,输出YES,否则输出NO。
Sample Input
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 1
2 2
4
-10 -10
-10 10
10 10
10 -10
3
100 100
1 1
2 2
Sample Output
YES
NO

分析

判断点是否在多边形内,这里使用的是二分法,时间复杂度O(logn)。如何二分?

我们可以将多边形的一个点作为原点,向其他几个点引出射线,将原多边形分成n-2个三角形(n为多边形顶点数)。

如此一来可以将问题分解为:

  1. 判断点在哪两个射线之间。
  2. 判断点是否在该三角形内。

这里用到数学几何上的一个知识点:向量叉乘

向量a,b的叉积结果是一个向量,计算结果是:
img

其中n是一个垂直于a和b构成的平面的单位向量。θ是向量a与b的夹角。满足右手定则。

顺便提一下向量点乘:
向量a,b的点积的结果是一个标量,若两个向量的夹角是θ,则
img

对于用坐标表示的向量a=(x1,y1),b=(x2,y2)来说,a×b的结果(一般讨论共起点)为:

x1*y2-x2*y1

  • 如果值大于0,说明向量b在a的逆时针方向(左手边)。
  • 如果值小于0,说明向量b在a的顺时针方向(右手边)。
  • 如果值为0,说明a与b共线。

如此,便可以写出计算叉乘的代码了

1
2
3
4
5
6
7
8
9
typedef struct point{
int x,y;
}point;
int cross(point p0,point p1,point p2){
//向量a,b的公共起点为p0,a终点为p1,b终点为p2。返回a×b的结果
//>0表示b在a的左边,<0表示b在a的右边,=0表示b与a共线
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

我们可以将第一个点作为原点,原点到各个顶点形成的射线看作若干向量,根据每个射线所在的向量以及原点与目标点组成的向量这两个向量的叉乘正负,二分所有射线,判断出目标点在哪两个射线之间,然后用类似思路判断是否在该三角形内即可。

在最一开始可以进行一个边界的判断,判断下目标点如果在第一个射线的左边,或者在最后一个射线的右边,那么这个点肯定不在多边形内。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
typedef struct point{
int x,y;
}point;
int cross(point p0,point p1,point p2){
//向量a,b的公共起点为p0,a终点为p1,b终点为p2。返回a×b的结果
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}
int main(){
int n,m;
point a[10005],b[10005];
while(cin>>n){
for(int i = 0;i<n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
}
cin>>m;
for(int i = 0;i<m;i++){
scanf("%d %d",&b[i].x,&b[i].y);
}
bool ans = true;
//判断每一个点的状态
for(int i = 0;i<m;i++){
//第一个向量与最后一个向量的边界判断
if(cross(a[0],a[1],b[i])>=0 || cross(a[0],a[n-1],b[i])<=0){
ans = false;
break;
}
int left = 2; //最后保证目标点在(a[0],a[left])向量的左边
int right = n-1;
while(left < right){
int mid = (left + right) >> 1;
if(cross(a[0],a[mid],b[i])>0) //点在(a[0],a[mid])的左边
right = mid;
else //点在(a[0],a[mid])的右边
left = mid + 1;
}
//保证目标点在(a[0],a[left])向量的左边,那么必然在(a[0],a[left-1]),(a[0],a[left])之间
if(cross(a[left],a[left-1],b[i])<=0){
ans = false;
break;
}

}
if(ans == true)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}