Loj 2549 战争

Posted on | Views:

闵可夫斯基和.

对于给出的两个点集可以分别做出两个凸包 $A,B$ ,

记询问给出的向量为 $w=(dx,dy)$ ,若存在向量 $a\in A,b\in B$ 满足 $a=b+w$ ,则会产生冲突.

即判断是否存在 $a\in A,b\in B$ 满足 $w=a-b$.

将 $B$ 中所有点关于原点对称得到 $-B$ ,那么 $A$ 与 $-B$ 的闵可夫斯基和就是所有 $a-b$ 的集合.

两个凸包的闵可夫斯基和仍是一个凸包,将两个凸包的边拿出来归并排序即可得到求和后的凸包.

有可能存在三点共线,所以归并排序后对点集再求一次凸包.

最后只需要判定 $w$ 是否在凸包内,将 $w$ 和凸包一起平移,使得凸包第一个点与原点重合.

先判断 $w$ 是否超出左右的边界,若在边界内,根据极角二分出凸包上相邻的两个点进行判断即可.

如图,红点和蓝点由叉积知在边界外,绿点可以用二分找出两个相邻的黄点,用叉积判断是否在凸包内.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
struct v2
{
	int x, y;
	v2(int x = 0, int y = 0) : x(x), y(y) {}
	v2 operator + (const v2 &rhs) const
	{
		return v2(x + rhs.x, y + rhs.y);
	} 	
	v2 operator - (const v2 &rhs) const
	{
		return v2(x - rhs.x, y - rhs.y);
	}
	ll operator * (const v2 &rhs) const
	{
		return 1LL * x * rhs.y - 1LL * y * rhs.x;
	}
	ll modulus()
	{
		return 1LL * x * x + 1LL * y * y;
	}
	friend bool operator < (v2 A, v2 B)
	{
		return A * B > 0 || (A * B == 0 && A.modulus() < B.modulus());
	}
};
const int N = 2e5 + 10;
v2 stk[N];
int tp;
void Convex(v2 *a, int &n)
{
	tp = 0;
	for (int i = 2; i <= n; ++i)
		if (a[i].y < a[1].y || (a[i].y == a[1].y && a[i].x < a[1].x))
			swap(a[i], a[1]);
	v2 tmp = a[1];
	for (int i = 1; i <= n; ++i)
		a[i] = a[i] - tmp;
	sort(a + 2, a + n + 1);
	for (int i = 1; i <= n; ++i)
	{
		while (tp >= 2 && (a[i] - stk[tp - 1]) * (stk[tp] - stk[tp - 1]) >= 0)
			--tp;
		stk[++tp] = a[i];		
	}
	n = tp;
	for (int i = 1; i <= n; ++i)
		a[i] = stk[i] + tmp;
	a[n + 1] = a[1];
}
bool InConvex(v2 p, v2 *a, int n)
{
	if (p * a[2] > 0 || a[n] * p > 0)
		return false;
	int pos = lower_bound(a + 1, a + 1 + n, p) - a - 1;
	return (p - a[pos]) * (a[pos + 1] - a[pos]) <= 0;
}
int n, m, q, tot = 0;
v2 A[N], B[N], C[N], e1[N], e2[N];
void Minkowski()
{
	for (int i = 1; i <= n; ++i)
		e1[i] = A[i + 1] - A[i];
	for (int i = 1; i <= m; ++i)
		e2[i] = B[i + 1] - B[i];
	C[tot = 1] = A[1] + B[1];
	int p1 = 1, p2 = 1;
	while (p1 <= n && p2 <= m)
		++tot, C[tot] = C[tot - 1] + (e1[p1] * e2[p2] >= 0 ? e1[p1++] : e2[p2++]);
	while (p1 <= n)
		++tot, C[tot] = C[tot - 1] + e1[p1++];
	while (p2 <= m)
		++tot, C[tot] = C[tot - 1] + e2[p2++];
	Convex(C, tot);
}
int main()
{
	n = read(), m = read(), q = read();
	for (int i = 1; i <= n; ++i)
		A[i].x = read(), A[i].y = read();
	Convex(A, n);
	for (int i = 1; i <= m; ++i)
		B[i].x = -read(), B[i].y = -read();
	Convex(B, m);
	Minkowski();
	v2 tmp = C[1];
	for (int i = 1; i <= tot; ++i)
		C[i] = C[i] - tmp;
	for (int i = 1; i <= q; ++i)
	{
		v2 p;
		p.x = read(), p.y = read();
		p = p - tmp;
		if (InConvex(p, C, tot))
			puts("1");
		else
			puts("0");
	}
	return 0;
}