专栏首页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算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 随机增量算法 - 最小圆覆盖

    随机增量算法是计算几何的一个重要算法,它对理论知识要求不高,算法时间复杂度低,应用范围广大。

    ACM算法日常
  • leetcode 题解 | 121. 买卖股票的最佳时机

    如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

    ACM算法日常
  • leetcode 50 | 实现pow函数

    就比如3的4次方,其实是3的平方乘以3的平方,依据算式3,那么就能写出递归的写法,注意如果n为奇数,n/2取整对丢失1,则有:

    ACM算法日常
  • 03 . MysSQL权限和备份

    恢复时间点之前首先将全量备份恢复之后,在此基础上回放增加的binlog直至指定的时间点

    常见_youmen
  • 创建你的第一个shell脚本

    安装自己的虚拟机或者买个什么云服务,有的也是很便宜。我之前买的一个云三年300多。

    田维常
  • 最佳实践 | 3个服务营销实例,教你轻松实现“增长”

    ? ? “增长”是近年来众多大小企业都面临的核心痛点,如何高效增长?如何持续增长?大家都在探索数字化时代的“增长”之道。 在实际业务环节中,客户触达、获客转...

    腾讯企点
  • 视频配音篇,如何使用百度翻译将文本转换为mp3语音?

    这里推荐使用Chrome浏览器,当然新版Edge也更换了Chrome内核,操作方式基本相同;

    zhaoolee
  • 聊聊spring-data-redis的连接池的校验

    spring-data-redis/2.0.10.RELEASE/spring-data-redis-2.0.10.RELEASE-sources.jar!/o...

    codecraft
  • 聊聊debezium的ChangeEventQueue

    debezium-v1.1.1.Final/debezium-core/src/main/java/io/debezium/connector/base/Cha...

    codecraft
  • 聊聊debezium的ChangeEventQueue

    debezium-v1.1.1.Final/debezium-core/src/main/java/io/debezium/connector/base/Cha...

    codecraft

扫码关注云+社区

领取腾讯云代金券