描述

灾区已经非常困难，灾民需要帐篷、衣物、食品和血浆。可通往灾区的道路到处都是塌方，70%以上的路面损坏，桥梁全部被毁。中国空军立即启动应急预案，展开史上最大强度非作战空运行动，准备向灾区空投急需物资。由于余震不断，天气恶劣，怎样知道空投的物资是否落在某灾区的区域内呢？经过空中观测，某灾区为一凸多边形，空投的物资落在 P(X,Y)点。你能否给出一个正确判断？

输入

第 1 行： N X Y (N 为凸形的边数，X，Y 为空投物资的坐标 )

第 2 行： X1 Y1 X2 Y2…….Xn Yn （逆序给出的 N 个顶点坐标 ）

约束条件:

（1） 3 ≤N ≤ 20

（2） 所有的坐标 Xi 和 Yi 为整数 -10000≤ Xi ，Yi ≤10000

（3） X,Y 为整数 -10000≤ X ，Y ≤10000

（4） 时间限制： 1000MS

 

输出

YES （物资落在灾区的区域内 ）

或

NO （物资落在灾区的区域外 ）

 

样例输入

4 2 2
-1 0 3 -2 10 9 -1 110

样例输出

YES

方法 1

判断一个点是否在指定区域内

在图像处理时，我们会经常需要判断一个点是否位于多边形区域内，这里介绍2种比较巧妙的算法。

射线法

第一种是射线法，算法思想非常巧妙：从待判断的点向某一个方向引射线，计算和多边形交点的个数，如果个数是偶数或者0则点在多边形外，如果是奇数，则在多边形内

这里有二种特殊情况：

1. 射线经过顶点：当射线经过顶点时，判断就会出现异常情况。

2. 点在边上：这种情况也不能用交点个数的奇偶性来判断了，要快速地判断这个点是否在边上。

方法2 (重点!)

我们可以把多边形可以看做是一条从某点出发的闭合路，可以观察到在内部的点永远都在路的同一边。

给定线段的两个点P0(x0,y0)和P1(x1,y1)，目标点P(x,y),它们有如下的关系：

计算(y - y0) (x1 - x0) - (x - x0) (y1 - y0)

如果答案小于0则说明P在线段的右边，大于0则在左边，等于0说明在线段上。

其他方法(不推荐)

比如面积法：就是计算所有边和目标点组成的三角形面积和是否等于总的多边形面积，如果相等，则点在该区域的内部。

这种方法计算量较大，多边形的面积计算也是比较麻烦；

还有夹角法：判断所有边和目标点的夹角和是否为360度，计算量同样很大。

#include <stdio.h>
#include <stdlib.h>

int main()
{
int x = 0,y = 0;

int X[20] = {0};
int Y[20] = {0};
int N = 0;
scanf("%d",&N);
scanf("%d %d",&x,&y);

int i = 0;
for(; i < N ; i++)
{
scanf("%d",&X[i]);
scanf("%d",&Y[i]);
}

int jud = 0;
i = 0;

/**
m (x,y)
给定 p(x0,y0)
给定 q(x1,y1)
满足 (y – y0) * (x1 – x0) – (x -x0) * (y1 – y0)
小于 0 在右边 大于零在左边 等于零 在线段上
*/

for(; i < N-1 ;i++)
{
jud = (y – Y[i]) * (X[i + 1] – X[i]) – (x – X[i]) * (Y[i+1] – Y[i]);
if(jud < 0)
{
printf("NO");
return 0;
}

}
printf("YES");

return 0;
}