经典结论,一个点 \(P(x, y)\) 在一个凸多边形内部 \(S = \{(x_i, y_i)\}\) 的充要条件是 \(\forall i \in [1, n], (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x - x_i, y - y_i) \ge 0\),其中 \(S\) 的点按照逆时针排列。
然后我们运用叉积的一个性质 \((x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x - x_i, y - y_i) = (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x, y) - (x_{i + 1} - x_i, y_{i + 1} - y_i) \times (x_i, y_i)\) 就做完了,预处理后项最大值即可。
code
// Problem: G - Intersection of Polygons
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, q, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], f[maxn], g[maxn];
inline ll calc(ll a, ll b, ll c, ll d) {
return a * d - b * c;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
}
scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld", &c[i], &d[i]);
}
a[n + 1] = a[1];
b[n + 1] = b[1];
scanf("%lld", &q);
for (int i = 1; i <= n; ++i) {
e[i] = a[i + 1] - a[i];
f[i] = b[i + 1] - b[i];
g[i] = -9e18;
for (int j = 1; j <= m; ++j) {
g[i] = max(g[i], calc(e[i], f[i], a[i] + c[j], b[i] + d[j]));
}
}
while (q--) {
ll x, y;
scanf("%lld%lld", &x, &y);
bool flag = 1;
for (int i = 1; i <= n; ++i) {
if (calc(e[i], f[i], x, y) < g[i]) {
flag = 0;
break;
}
}
puts(flag ? "Yes" : "No");
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}