# 丘比特的箭（点是否在面内）- HDU 1756

（红心点为A，右边有3个点，说明在多边形内部）

（向量的乘积）

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

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

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

（P1A的斜率大于P1P2的斜率）

Problem Description

Input

Output

Sample Input

4

10 10

20 10

20 5

10 5

2

15 8

25 8

Sample Output

Yes

No

``````#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算法日常

0 条评论

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

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

• ### Mathematica 爱心首饰 III: 爱神之箭的瞬间

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

• ### 丘比特的神箭续

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

• ### 周末组局玩狼人杀，这些小程序你绝对用得上！

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

• ### 程序员进阶之算法练习（十三）

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

• ### 程序员进阶之算法练习（十一）有感而发

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

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

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

• ### 星空下的新赛点，民营航空迎来新机会

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

• ### Kali Linux渗透基础知识整理(一):信息搜集（一）

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

• ### 神舟十二号飞天｜扒一扒火箭上的摄像头：有多少？装在哪？有何用？

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

• ### 「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 算法，剩下的都是高级...

• ### 火眼金睛 | 应用崩溃惯用三大杀招，你中招了么？

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

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

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

• ### 疫情之下，循环之路开启

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