Cupid's Arrow

2024-02-27 04:20
文章标签 arrow cupid

本文主要是介绍Cupid's Arrow,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传说世上有一支丘比特的箭,凡是被这支箭射到的人,就会深深的爱上射箭的人。
世上无数人都曾经梦想得到这支箭。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

      给你一个n边形的坐标,然后给你m个点的坐标,问这m个点是否全在这个多边形

     

      将一个多边形,以其中一个点为原点,开始与其他各点相连并延长做射线,则会形成许多个三角形区域。(如左图)

      这样我们可以先判断点在哪两条向量之间。用二分查找,可以很快搜索到。

      当然,首先要判断点是否在最左边向量左侧或者最右边向量右侧,如是,则点不在多边形内。

      以右图为例,我们找到紫色点在左数第一个三角形区域内,绿色点在左数第二个三角形区域内。

      然后,再判断下图所示线段与 所判断点的位置关系。

     绿色的线段可以判断绿色的点,左边紫色的点也由相应的线段来判断位置关系。

    这样可以判断点是否在多边形内啦。

    总结一下:

   ①建立一个个三角形区域,用其中两条边判断点所在大体区域。

   

#include <stdio.h>
struct point
{double x,y;
}a[100005],b[100005];
double cross(point p0,point p1,point p2)//以p0为角的起始点,通过边的斜率来判断相对位置
{return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}int main()
{int n,m,i,low,high,mid,flag;while( scanf("%d",&n)!=EOF ){for( i=0 ; i<n ; ++i )scanf("%lf%lf",&a[i].x,&a[i].y);scanf("%d",&m);for( i=0 ; i<m ; ++i )scanf("%lf%lf",&b[i].x,&b[i].y);flag=0;for( i=0 ; i<m ; ++i ){// ① 判断初始时,点是否在凸多边形两最外侧边外面if( cross(a[0],a[1],b[i])>=0 || cross(a[0],a[n-1],b[i])<=0 ){flag=1;break;}// ② 判断凸多边形在哪个三角形里头low=2;high=n-1;while( low<high ){mid=(low+high)>>1;      // 就是除以2,比除以2快(位运算比乘除快很多)if( cross(a[0],a[mid],b[i])>0 )high=mid;elselow=mid+1;}// 查看b是否在凸多边形上面那些边的外面if( cross(a[low],a[low-1],b[i])<=0 ){flag=1;break;}}if(flag)    printf("NO\n");else    printf("YES\n");}return 0;
}

②用第三条边来判断点是否在多边形内。

这篇关于Cupid's Arrow的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/751197

相关文章

CocosCreator物理引擎Demo源码分析(3)-stick-arrow

CocosCreator开发笔记(8)-读取和解析JSON数据文件 Box2D C++ 三种作用力效果 ApplyForce、ApplyLinearImpulse、SetLinearVelocity stick-arrow示例展示了如何动态发射刚体飞往目标点。 技术点 1、触摸屏幕发射刚体,计算起点和目标点的夹角,设置刚体的线性速度。 2、在Update中不断施加一个作用力到刚体尾部

Apache Arrow简介

是什么? (1) Apache Arrow是内存分析开发平台,是Apache的顶级项目。 (2) Apache Arrow是一个开源的跨平台数据层开发框架,主要提供高效的、硬件加速的、内存中数据计算的能力。Apache Arrow的设计初衷是作为“新一代大数据系统的共享基础”,可以作为不同系统之间进行高效数据交换的媒介,同时提供快速、低延迟的数据访问接口。Apache Arrow的主要目标

基于 apache-arrow 的 duckdb rust 客户端

背景 duckdb 是一个 C++ 编写的单机版嵌入式分析型数据库。它刚开源的时候是对标 SQLite 的列存数据库,并提供与 SQLite 一样的易用性,编译成一个头文件和一个 cpp 文件就可以在程序中使用,甚至提供与 SQLite 兼容的接口,因此受到了很多人的关注。 本文介绍笔者近期开发的 duckdb-rs 库,让大家可以很方便地在 rust 代码库中使用 duckdb 的功能。 li

ES6新特性箭头函数(Arrow Function)

箭头函数是ECMAScript 6最受关注的更新内容之一。它引入了一种用「箭头」(=>)来定义函数的新语法,它…它碉堡了~。箭头函数与传统的JavaScript函数主要区别在于以下几点: 1.对 this 的关联。函数内置 this 的值,取决于箭头函数在哪儿定义,而非箭头函数执行的上下文环境。 2.new 不可用。箭头函数不能使用 new 关键字来实例化对象,不然会报错。 3.

引导页面的移动箭头效果 guide arrow animation

要实现类似效果 由于动画是非平滑的,所以不能用平移的方式来实现,这里就定时去更新在父布局的位置来是实现 先看布局代码 <RelativeLayoutandroid:id="@+id/swipe_layout"android:layout_width="wrap_content"android:layout_height="wrap_content"android:layout_gr

Applicative与Arrow

原文说得非常清楚,不翻译效果可能更好。 进入ghci  > :m + Control.Applicative Control.Arrow Control.Applicative Control.Arrow>filter ((>2) &&& (<7) >>> uncurry (&&)) [1..10] [3,4,5,6] We have two mysterious operators

HDU 1756 Cupid's Arrow 判断点在多边形的内部

Cupid's Arrow Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1163    Accepted Submission(s): 425 Problem Description 传说世上有一支丘比特的箭,凡是被这支箭射到的人

HDU 1756 Cupid's Arrow(判断点是否在多边形内部)

Cupid's Arrow Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 702    Accepted Submission(s): 252 Problem Description 传说世上有一支丘比特的箭,凡是

arrow,一个神奇的 Python 库!

更多资料获取 📚 个人网站:ipengtao.com 大家好,今天为大家分享一个神奇的 Python 库 - arrow。 Github地址:https://github.com/arrow-py/arrow 日期和时间处理是许多应用程序中的常见任务,但在 Python 中,标准库中的 datetime 模块有时可能会让这些任务变得复杂和繁琐。幸运的是,有一个名为 Arrow 的

0062【Edabit ★☆☆☆☆☆】Arrow Functions

0062【Edabit ★☆☆☆☆☆】Arrow Functions closures higher_order_functions language_fundamentals logic Instructions In the Code tab you will find code that is missing a single character in order to pass t