称号：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1429
Description
已知一个凸多边形A（包括n个点，点依照顺时针给出）。和一个点集B（包括m个点），请推断这m个点是否都严格在凸多边形A内部。Input
输入包括多组測试数据。
对于每组測试数据：
第1行。包括一个整数n (3 ≤ n ≤ 105)代表着凸多边形A的点的数量。
接下来n行每行包括一个坐标(x, y) (-109 ≤ x, y ≤ 109) 表示这个凸多边形，点依照顺时针给出。
第n + 2行。包括一个整数m (3 ≤ m ≤ 105)代表着点集B的点的数量。
接下来m行每行包括一个坐标(x, y) (-109 ≤ x, y ≤ 109) 表示这个点集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(n)，此方法复杂度仅为O（logn）。
并且对于推断非常多点是否在多边形内，就能够用这样的方法了，耗时少。
原理：
将一个多边形，以当中一个点为原点，開始与其它各点相连并延长做射线。则会形成很多个三角形区域。（如左图）
这样我们能够先推断点在哪两条向量之间。用二分查找，能够非常快搜索到。
当然，首先要推断点是否在最左边向量左側或者最右边向量右側，如是。则点不在多边形内。
以右图为例，我们找到紫色点在左数第一个三角形区域内，绿色点在左数第二个三角形区域内。
然后，再推断下图所看到的线段与 所推断点的位置关系。
绿色的线段能够推断绿色的点。左边紫色的点也由对应的线段来推断位置关系。
这样能够推断点是否在多边形内啦。
总结一下：
①建立一个个三角形区域。用当中两条边推断点所在大体区域。
②用第三条边来推断点是否在多边形内。
二分查找就是用在了第一条的地方，用来查找大体区域位置。
明确了这个，就能够做对应的题目来练习一下了！
就是这道题~。~
#include <stdio.h>
struct point
{
double x,y;
}a[100005],b[100005];
double cross(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
int n,m,i,low,high,mid,flag;
while( scanf("%d",&n)!=EOF )
{
for( i=0 ; i<n ; ++i )
scanf("%lf%lf",&a[i].x,&a[i].y);
scanf("%d",&m);
for( i=0 ; i<m ; ++i )
scanf("%lf%lf",&b[i].x,&b[i].y);
flag=0;
for( i=0 ; i<m ; ++i )
{
// ① 推断初始时，点是否在凸多边形两最外側边外面
if( cross(a[0],a[1],b[i])>=0 || cross(a[0],a[n-1],b[i])<=0 )
{
flag=1;
break;
}
// ② 推断凸多边形在哪个三角形里头
low=2;high=n-1;
while( low<high )
{
mid=(low+high)>>1; // 就是除以2。比除以2快(位运算比乘除快非常多）
if( cross(a[0],a[mid],b[i])>0 )
high=mid;
else
low=mid+1;
}
// 查看b是否在凸多边形上面那些边的外面
if( cross(a[low],a[low-1],b[i])<=0 )
{
flag=1;
break;
}
}
if(flag) printf("NO
");
else printf("YES
");
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。