凸多边形

Bertha 。 2021-09-26 15:22 380阅读 0赞

题目：

## 问题 : 凸多边形 ##

时间限制: 1 Sec  内存限制: 128 M

## 题目描述 ##

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

## 输入 ##

第1行： N X Y (N为凸形的边数，X，Y为空投物资的坐标 )  
第2行： X1 Y1 X2 Y2…….Xn Yn （逆序给出的N个顶点坐标 ）

## 输出 ##

YES （物资落在灾区的区域内 ）  
或  
NO （物资落在灾区的区域外 ）  
【约束条件】  
（1） 3 ≤N ≤ 20  
（2） 所有的坐标Xi和Yi为整数 -10000≤ Xi ，Yi ≤10000  
（3） X,Y为整数 -10000≤ X ，Y ≤10000

（4） 时间限制： 1000MS

当物资降落在区域边缘时，输出YES。

## 样例输入 ##

## 样例输出 ##

题目描述：

本题解题方法引用的是这篇博客的原文：[点击打开链接][Link 1]，引用只是为了复习使用，如有冒犯，请联系我删除。

求一个给定的点A(x0,y0)是否在凸多边型p0p1...pn-1（逆序给出）内部，我们首先想到的是判断一个三角形三个点是顺时针还是逆时针的，我们可以利用这个结论。

看图：![1366474095_7002.jpg][]

如果点A在多边形内部，则三角形APiP(i+1%n)必为逆时针，而如果在外部，则有些点和A组成的三角形是顺序的，多以，我们只需要依次判断APiP(i+1%n)是否为逆时针即可，一旦发现不是逆时针，则说明在凸多边型外部！

那么我们来看怎么判断三角形的正序还是逆序呢？我们有以下结论：定义向量AB=（x1,y1),AC=（x2,y2），则：  
AB X AC>0  逆时针

AB X AC<0  顺时针，其中运算X（向量叉乘）定义为x1\*y2-x2\*y1。

代码：

#include<stdio.h>
    #include<string.h>
    int main()
    {
        int d1,d2,w1,w2,n,x,y,x1,y1,x2,y2,flag;
        int i;
        int a[50],m[50];
        while(scanf("%d%d%d",&n,&x,&y)!=EOF){
        	for(i = 0;i < n;i++)
        		scanf("%d%d",&a[i],&m[i]);
        	flag= 1; 
        	for(i = 0;i < n;i ++){
        		d1 = a[i],d2 = m[i];
        		w1 = a[(i+1)%n],w2 = m[(i+1)%n];
        		x1 = d1 - x,y1 = d2 - y;
        		x2 = w1 - x,y2 = w2 - y;
        		int w = x1*y2-x2*y1;
        		flag = w >= 0 ? 1 : 0;
        		if(!flag)
        			break;
    		}
    		if(flag)
    			printf("YES\n");
    		else
    			printf("NO\n");
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/ych1035235541/article/details/8829865
[1366474095_7002.jpg]: https://img-my.csdn.net/uploads/201304/21/1366474095_7002.jpg