首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >丘比特的神箭续

丘比特的神箭续

作者头像
ACM算法日常
发布2020-07-14 15:53:23
3500
发布2020-07-14 15:53:23
举报
文章被收录于专栏:ACM算法日常ACM算法日常

《丘比特的神箭》中我们考虑了点和任意多边形的关系的 算法. 如果限制多边形为凸多边形的话,其实是有 算法的. 本文就来考虑这个问题. 例题来自 Hrbustoj 1429 凸多边形

分析

凸多边形
Description
已知一个凸多边形A(包含n个点,点按照顺时针给出),和一个点集B(包含m个点),
请判断这m个点是否都严格在凸多边形A内部。所谓严格内部,就是点不能在多边形边上

Input
输入包含多组测试数据。
对于每组测试数据:
第1行,包含一个整数n (3 ≤ n ≤ 1e5)代表着凸多边形A的点的数量。
接下来n行每行包含一个坐标(x, y) (-1e9 ≤ x, y ≤ 1e9) 表示这个凸多边形,点按照顺时针给出。
第n + 2行,包含一个整数m (3 ≤ m ≤ 1e5)代表着点集B的点的数量。
接下来m行每行包含一个坐标(x, y) (-1e9 ≤ x, y ≤ 1e9) 表示这个点集B。
处理到文件结束

Output
对于每组测试数据:
第1行,如果点集B都严格在凸多边形A内,输出YES,否则输出NO。

Sample Input
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 1
2 2
4
-10 -10
-10 10
10 10
10 -10
3
100 100
1 1
2 2

Sample Output
YES
NO

Author
齐达拉图@HRBUST

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

这种算法的

  • 时间复杂度:
  • 适用范围:凸多边形,不需要考虑精度误差,但需要考虑多边形的顶点给出的顺序(例如本题是顺时针给出).

算法思想:

  1. 任意选取凸多边形的一个顶点作为起点(例如本题选取读入数据的第一个顶点P[0]即可,也就是下图中的 A). 连接它和其他顶点做射线. 例如下图
  1. 首先判断一下待判断点 P 是否在 和 之间. 判断的方法也很简单, 能在 和 之间的充要条件就是 如果不满足的话,直接返回 false. 注意,上图中, B = P[1], E = P[n-1]
  2. 然后二分计算 最大的 满足 即 在 和 之间,判断的准则是 如上图所示,这个
  3. 那么 P 严格在该凸多边形内的充要条件就是 线段 AP 和线段 P[i]P[i+1] 不相交(不是规范相交也不是非规范相交).

下面开始写代码

//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma warning(disable:4996)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <ctype.h>
#include <string.h>
#include <fstream>
#include <sstream>
#include <math.h>
#include <map>
//#include <unordered_map>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#include <stdlib.h>
#include <bitset>
using namespace std;
//#define int unsigned long long
//#define int long long
#define re register int
#define ci const int
#define ui unsigned int 
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ild inline double
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
#define SQUARE(x) ((x) * (x))
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;
typedef map<int, int>::iterator mit;
const int inf = ~0u>>1;
const double PI = acos(-1.0), eps = 1e-6;
namespace fastio
{
 const int BUF = 1 << 21;
 char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
 ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
 ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
 ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
 ili read(int &x)
 {
  x = 0; int f = 1; char c = gc(); if (!~c) return EOF;
  while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
  while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
  x *= f; return 1;
 }
 ili read(double &x) 
 {
  int xx = 0; double f = 1.0, fraction = 1.0; char c = gc(); if (!~c) return EOF;
  while (!isdigit(c)) { if (c == '-') f = -1.0; c = gc(); }
  while (isdigit(c)) { xx = (xx << 3) + (xx << 1) + (c ^ 48), c = gc(); }
  x = xx;
  if (c ^ '.') { x = f * xx; return 1; }
  c = gc();
  while (isdigit(c)) x += (c ^ 48) * (fraction /= 10), c = gc();
  x *= f; return 1;
 }
 ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
 ilv writeln(int x) { write(x);pc(10); }
 ili read(char *x)
 {
  char c = gc(); if (!~c) return EOF;
  while(!isalpha(c) && !isdigit(c)) c = gc();
  while (isalpha(c) || isdigit(c)) *x++ = c, c = gc();
  *x = 0; return 1;
 }
 ili readln(char *x)
 {
  char c = gc(); if (!~c) return EOF;
  while(c == 10) c = gc();
  while(c >= 32 && c <= 126) *x++ = c, c = gc();
  *x = 0; return 1;
 }
 ilv write(char *x) { while(*x) pc(*x++); }
 ilv write(const char *x) { while(*x) pc(*x++); }
 ilv writeln(char *x) { write(x); pc(10); }
 ilv writeln(const char *x) { write(x); pc(10); }
 ilv write(char c) { pc(c); }
 ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
#define cp const Point
const int maxn = 1e5+5;
int n, m;
struct Point
{
 double x, y;
 Point(double x = 0, double y = 0):x(x), y(y){}
 Point operator - (cp &o) const
 {
  return Point(x - o.x, y - o.y);
 }
 double operator / (cp &o) const
 {
  return x * o.y - y * o.x;
 }
} ps[maxn];

ild direction(cp &p1, cp &p2, cp &p3)
{
 return (p2 - p1) / (p3 - p1);
}

ili dcmp(double x)
{
 if (fabs(x) < eps) return 0;
 return x < 0 ? -1 : 1;
}

ili onsegment(cp &p1, cp &p2, cp &p3)
{
 return min(p1.x, p2.x) <= p3.x && p3.x <= max(p1.x, p2.x) && min(p1.y, p2.y) <= p3.y && p3.y <= max(p1.y, p2.y);
}

ili intersect(cp &p1, cp &p2, cp &p3, cp &p4)
{
 double d1 = direction(p1, p2, p3);
 double d2 = direction(p1, p2, p4);
 double d3 = direction(p3, p4, p1);
 double d4 = direction(p3, p4, p2);
 if (dcmp(d1 * d2) + dcmp(d3 * d4) == -2) return 1;
 if (!dcmp(d1) && onsegment(p1, p2, p3)) return 1;
 if (!dcmp(d2) && onsegment(p1, p2, p4)) return 1;
 if (!dcmp(d3) && onsegment(p3, p4, p1)) return 1;
 if (!dcmp(d4) && onsegment(p3, p4, p2)) return 1;
 return 0;
}

ili bw(cp &p1, cp &p2, cp &p3, cp &p) // p1p 是不是严格在 p1p2、p1p3 之间
{
 return dcmp(direction(p1, p2, p) * direction(p1, p, p3));
}

ili inpoly(cp &p)
{
 if (bw(ps[0], ps[1], ps[n - 1], p) ^ 1) return 0;
 int lo = 1, hi = n - 2, mid, ans = 1;
 while (lo <= hi)
 {
  mid = lo + hi >> 1;
  if (~bw(ps[0], ps[1], p, ps[mid]))
  {
   lo = mid + 1;
   ans = mid;
  }
  else
  {
   hi = mid - 1;
  }
 }
 return !intersect(ps[0], p, ps[ans], ps[ans + 1]);
}

signed main()
{
#ifdef LOCAL
 FILE *ALLIN = freopen("d:\\data.in", "r", stdin);
 //    freopen("d:\\my.out", "w", stdout);
#endif
 while (~read(n))
 {
  for (re i = 0; i < n; i++) read(ps[i].x), read(ps[i].y);
  read(m);
  Point p;
  int ans = 1;
  while (m--)
  {
   read(p.x), read(p.y);
   if (!ans)
   {
    continue;
   }
   ans = inpoly(p);
  }
  ans ? writeln("YES") : writeln("NO");
 }
 flush();
#ifdef LOCAL
 fclose(ALLIN);
#endif
 return 0;
}

ac情况

Accepted G++ 76ms 4072k
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-07-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 《丘比特的神箭》中我们考虑了点和任意多边形的关系的 算法. 如果限制多边形为凸多边形的话,其实是有 算法的. 本文就来考虑这个问题. 例题来自 Hrbustoj 1429 凸多边形
  • 分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档