凸多边形-白红宇的个人博客

凸多边形

发布日期：2021-07-01 00:13:20 浏览次数：2 分类：技术文章

本文共 1138 字，大约阅读时间需要 3 分钟。

问题 : 凸多边形

时间限制: 1 Sec

内存限制: 128 MB

题目描述

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

转载地址：https://lzyws739307453.blog.csdn.net/article/details/80024926 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：cut sticks

下一篇：负载平衡

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！