凸多边形
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 飞. 所以亟需能在 时间内判断点和凸多边形关系的算法.
这种算法的
算法思想:
下面开始写代码
//#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