考虑对两个点集求出凸包,显然如果这两个凸包相离就合法,然后问题就转化成了这两个凸包是否有交。
设红点凸包包围的点集为 \(A\),蓝点凸包包围的点集为 \(B\),问题为询问是否 \(\exists a \in A,b \in B,a=b\),即 \(a-b=0\)。
于是对所有蓝点取反,求出新的蓝点凸包,再与红点凸包计算它们闵可夫斯基和的凸包,如果 \((0,0)\) 在它的内部(包含边界),就说明 \(A\) 和 \(B\) 有交,输出 No
;否则输出 Yes
。
时间复杂度 \(O((n + m) \log (n + m))\),瓶颈在于对点排序。
code
const int maxn = 510;
int n, m, stk[maxn], top;
struct node {
int x, y;
node(int a = 0, int b = 0) : x(a), y(b) {}
};
node operator + (node a, node b) {
return node(a.x + b.x, a.y + b.y);
}
node operator - (node a, node b) {
return node(a.x - b.x, a.y - b.y);
}
int operator * (node a, node b) {
return a.x * b.y - a.y * b.x;
}
bool cmp(node a, node b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
vector<node> convex(vector<node> vc) {
sort(vc.begin(), vc.end(), cmp);
top = 0;
int n = (int)vc.size();
if (n == 1) {
return vc;
}
for (int i = 0; i < n; ++i) {
while (top >= 2 && (vc[stk[top]] - vc[stk[top - 1]]) * (vc[i] - vc[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
vector<node> res;
for (int i = 1; i < top; ++i) {
res.pb(vc[stk[i]]);
}
top = 0;
for (int i = n - 1; ~i; --i) {
while (top >= 2 && (vc[stk[top]] - vc[stk[top - 1]]) * (vc[i] - vc[stk[top - 1]]) <= 0) {
--top;
}
stk[++top] = i;
}
for (int i = 1; i < top; ++i) {
res.pb(vc[stk[i]]);
}
return res;
}
vector<node> mkfsj(vector<node> a, vector<node> b) {
int n = (int)a.size(), m = (int)b.size();
vector<node> va(n), vb(m), res;
res.pb(a[0] + b[0]);
for (int i = 0; i < n; ++i) {
va[i] = a[(i + 1) % n] - a[i];
}
for (int i = 0; i < m; ++i) {
vb[i] = b[(i + 1) % m] - b[i];
}
int i = 0, j = 0;
while (i < n && j < m) {
res.pb(res.back() + (va[i] * vb[j] >= 0 ? va[i++] : vb[j++]));
}
while (i < n) {
res.pb(res.back() + va[i++]);
}
while (j < m) {
res.pb(res.back() + vb[j++]);
}
res.erase(res.begin());
return res;
}
bool check(vector<node> a, vector<node> b) {
vector<node> res = mkfsj(a, b);
node O;
int n = (int)res.size();
for (int i = 1; i < n; ++i) {
if ((O - res[i - 1]) * (res[i] - res[i - 1]) > 0) {
return 0;
}
}
return 1;
}
void solve() {
vector<node> a, b;
for (int i = 0, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
a.pb(node(x, y));
}
for (int i = 0, x, y; i < m; ++i) {
scanf("%d%d", &x, &y);
b.pb(node(-x, -y));
}
vector<node> v1 = convex(a), v2 = convex(b);
puts(check(v1, v2) ? "No" : "Yes");
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
solve();
}
return 0;
}