凸多边形_牛客博客

问题 : 凸多边形

时间限制: 1 Sec 内存限制: 128 MB
</center>

题目描述

灾区已经非常困难，灾民需要帐篷、衣物、食品和血浆。可通往灾区的道路到处都是塌方，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。

样例输入

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

样例输出

YES

#include <stdio.h>
int main()
{
    int n, x, x1, x2, y, y1, y2, flag, s[25][2];
    while (~scanf("%d", &n))
    {
        flag = 0;
        scanf("%d%d", &x, &y);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &s[i][0], &s[i][1]);
        for (int i = 0; i < n; i++)
        {
            x1 = s[i][0];
            y1 = s[i][1];
            x2 = s[(i + 1) % n][0];
            y2 = s[(i + 1) % n][1];
            if ((y - y1) * (x2 - x1) - (x - x1) * (y2 - y1) < 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag)
            puts("NO");
        else puts("YES");
    }
    return 0;
}