专栏首页ACM算法日常丘比特的箭(点是否在面内)- HDU 1756

丘比特的箭(点是否在面内)- HDU 1756

对于点A是否在多边形P内的判定, 一般有两种方法:射线法和转角法。 这里介绍一下射线法

射线法:从点A出发作一条射线,计算这条射线与多边形P的边的交点数量N,如果N为奇数,则点A在多边形P内,否则在P外部。

射线法中这条射线是任意方向的,一般在编程的时候选取从A出发往X坐标轴正方向的一条射线X

(红心点为A,右边有3个点,说明在多边形内部)

射线法的原理:直线不可能从内部再次进入多边形,或从外部再次穿出多边形,即连续两次穿越边界的情况必然成对(大概就是这个意思,不是严格证明)。

射线法具体逻辑见源代码,涉及到几个子问题,大概说一下。

子问题1:判定点A在线段P1P2上(特殊处理点在边上的情况使用)。

两个向量a和b的叉积写作a^b = |a| |b|sinα (α为a,b向量之间的夹角)

叉积的几何意义:

对于向量AP1与向量AP2,如果叉积为0,说明夹角为0,也就是共线。

另外还要注意向量a、b的乘积a·b。

(向量的乘积)

乘积的几何意义:

a·b>0 方向基本相同,夹角在0°到90°之间

a·b=0 正交,相互垂直

a·b<0 方向基本相反,夹角在90°到180°之间

子问题2:判断点A在线段P1P2的左边。

对于线段P1P2的斜率k,如果P1A的斜率k'大于k,则A在线段P1P2的左边。

(P1A的斜率大于P1P2的斜率)

Problem Description

传说世上有一支丘比特的箭,凡是被这支箭射到的人,就会深深的爱上射箭的人。

世上无数人都曾经梦想得到这支箭。Lele当然也不例外。不过他想,在得到这支箭前,他总得先学会射箭。

日子一天天地过,Lele的箭术也越来越强,渐渐得,他不再满足于去射那圆形的靶子,他开始设计各种各样多边形的靶子。

不过,这样又出现了新的问题,由于长时间地练习射箭,Lele的视力已经高度近视,他现在甚至无法判断他的箭射到了靶子没有。所以他现在只能求助于聪明的Acmers,你能帮帮他嘛?

Input

本题目包含多组测试,请处理到文件结束。

在每组测试的第一行,包含一个正整数N(2<N<100),表示靶子的顶点数。

接着N行按顺时针方向给出这N个顶点的x和y坐标(0<x,y<1000)。

然后有一个正整数M,表示Lele射的箭的数目。

接下来M行分别给出Lele射的这些箭的X,Y坐标(0<X,Y<1000)。

Output

对于每枝箭,如果Lele射中了靶子,就在一行里面输出"Yes",否则输出"No"。

Sample Input

4

10 10

20 10

20 5

10 5

2

15 8

25 8

Sample Output

Yes

No

源代码:G++ 0ms

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const double eps = 1e-6;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}

    //向量+
    Point operator +(const Point &b)const
    {
        return Point(x + b.x, y + b.y);
    }

    //向量-
    Point operator -(const Point &b)const
    {
        return Point(x - b.x, y - b.y);
    }

    //点积
    double operator *(const Point &b)const
    {
        return x * b.x + y * b.y;
    }

    //叉积
    double operator ^(const Point &b)const
    {
        return x * b.y - b.x * y;
    }
};

static Point polygons[105];

//三态函数,判断两个double在eps精度下的大小关系
int dcmp(double x)
{
    if (fabs(x) < eps) return 0;
    else
        return x < 0 ? -1 : 1;
}

//判断点Q是否在P1和P2的线段上
bool is_in_line(Point P1, Point P2, Point Q)
{
    return dcmp((P1 - Q) ^ (P2 - Q)) == 0 && dcmp((P1 - Q) * (P2 - Q)) <= 0;
}

//判断点P在多边形内-射线法
bool is_in_polygon(Point P, int point_count)
{
    bool flag = false;

    for (int i = 1, j = point_count; i <= point_count; j = i++)
    {
        //多边形一条边的两个顶点
        Point P1 = polygons[i];
        Point P2 = polygons[j];

        //点在多边形一条边上
        if (is_in_line(P1, P2, P)) {
            return true;
        }
        //在多边形里面
        //以P点做一条水平向右的射线

        //1、线段在点的上下,而不是一边
        bool isUpDownLine = (dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0);

        if (isUpDownLine) {
            //2、点在射线与线段交点的左边
            //直线应该是y=kx+b吧
            //假如当前点是坐标是x1,y1,那么y>kx+b就说明点在直线左边,反之在右边
            /*
            p.x < (p.y-p1.y)/k + p1.x
            k*p.x < p.y-p1.y + k*p1.x
            p.y-p1.y + k*(p1.x-p.x) > 0
            p.y-p1.y > k*(p.x-p1.x)
            对于如果向量P1P的斜率大于P1P2的斜率,则P在P1P2的左边
            */
            bool isLeft = dcmp(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0;

            if (isLeft) { 
                flag = !flag;
            }
        }
    }

    return flag;
}

int main()
{
    int case_count, point_count;

    while (~scanf("%d", &point_count))
    {
        for (int i = 1; i <= point_count; i++) {
            scanf("%lf %lf", &polygons[i].x, &polygons[i].y);
        }

        Point point;
        scanf("%d", &case_count);

        while (case_count--)
        {
            scanf("%lf %lf", &point.x, &point.y);
            //判断是否在多边形里面
            if (is_in_polygon(point, point_count)) {
                printf("Yes\n");
            }
            else {
                printf("No\n");
            }
        }
    }
    return 0;
}
文章分享自微信公众号:
ACM算法日常

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • WPF 基础 2D 图形学知识 判断点是否在任意几何内部方法

    对于任意的几何图形,如四边形,已知几何的顶点,求给定的一个点是否在几何之内的方法有多个,有 WPF 专用部分以及通用算法部分,有通用算法部分在 UWP 和 Xa...

    林德熙
  • Mathematica 爱心首饰 III: 爱神之箭的瞬间

    在我的上一文中,我开发了一种基于流体的首饰挂件。后来我在想,也许我应该再做一件基于固体的首饰。

    WolframChina
  • 丘比特的神箭续

    本题数据量较大,如果使用 的算法将被 T 飞. 所以亟需能在 时间内判断点和凸多边形关系的算法.

    ACM算法日常
  • 周末组局玩狼人杀,这些小程序你绝对用得上!

    狼人杀这款桌游,从去年开始火了起来。一时间,各种狼人杀 app 纷纷上线。你是否也中了狼人杀的毒呢?

    知晓君
  • 星际2中复刻DOTA白虎

    逍遥剑客
  • 程序员进阶之算法练习(十三)

    前言 比赛就在这周末,这篇是比赛前最后一篇训练总结。 正文 hdu 5980(简单题) 题目大意 一个32位的数字,每个bytes包括8bit,所以一个整...

    落影
  • 从产品的三个阶段全方位解析产品运营体系

    用户1756920
  • 程序员进阶之算法练习(十一)有感而发

    前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

    落影
  • 一文读懂PLC的通讯方式-AB以太网拓扑方式

    一直以来,PLC跟其他设备的通讯方式都是自动化工程师入门学习的难点和要点。说它难,因为这里面牵扯到了数据通讯的一些知识,说它重要,因为大多数自动控制现场不会单独...

    剑指工控
  • 星空下的新赛点,民营航空迎来新机会

    从去年开始,社区团购的生意成了互联网巨头们争抢的重点,巨头们都手持巨大资源和资金入场,抢夺着菜篮子中那几毛钱的利益。但在巨头纷纷下场的同时,也有不少人发出了“只...

    刘旷
  • Kali Linux渗透基础知识整理(一):信息搜集(一)

    收集渗透目标的情报是最重要的阶段。如果收集到有用的情报资料的话,可以大大提高对渗透测试的成功性。收集渗透目标的情报一般是对目标系统的分析,扫描探测,服务查点,扫...

    网e渗透安全部
  • 神舟十二号飞天|扒一扒火箭上的摄像头:有多少?装在哪?有何用?

    根据中国载人航天工程办公室发布的消息,航天员聂海胜、刘伯明、汤洪波乘神舟十二号载人飞船前往空间站天和核心舱。按计划,他们将在太空驻留长达三个月。

    AI掘金志
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津
  • 客户端基本不用的算法系列:RMQ问题 - ST 算法

    今天的算法可能有点难,但是如果我们只需要会使用 RMQ 问题的 ST 算法模板,这种程度就已经可以了!因为 RMQ 问题除了最优解的 ST 算法,剩下的都是高级...

    用户2932962
  • 火眼金睛 | 应用崩溃惯用三大杀招,你中招了么?

    应用崩溃时,没有一句废话,不留一点痕迹,悄无声息,隐身而去,毫不留情。说它是用户流失的冷血杀手一点也不为过。它不光冷血,还带着深不可测的神秘感,让人难以揣摩。 ...

    腾讯Bugly
  • 武大50名学生将卫星送上天!用了老师800万科研经费,搭长征八号“顺风车”升空

    晓查 萧箫 发自 凹非寺 量子位 | 公众号 QbitAI 一趟火箭载着22颗卫星成功上天,长征八号这次又刷新了一波历史纪录。 而且其中一项,还是武汉大学参与...

    量子位
  • 疫情之下,循环之路开启

    —R.J.帕拉西奥《奇迹...

    小Bob来啦

扫码关注腾讯云开发者

领取腾讯云代金券