JSOI2018 战争 | Kyons'Blog 




 
 
 
 



 
 



JSOI2018 战争

大意

为了阻止战争,你就是,天选之人~~

解析

假设$a\in A,b\in B$,存在向量$w$,使得$b+w=a$,那么根据闵可夫斯基差,可以得到$A-B=\{w\rvert w+B\subseteq A\}$
当然,解题都是怎么方便怎么来,我们直接将$B$取反,然后和$A$求个闵可夫斯基和就完事了.
最后再判断所给点在不在C里,就完事了
哦,要对$A,B$进行一次求凸包,去掉边上的点
然后再对$C$求一次.

代码

代码戳我戳我
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;
const double pi = acos(-1.0);
const double inf = 1e100;
const double eps = 1e-12;
typedef struct point vec; //向量vec
struct point { //点的基本数据结构
double x, y;
double poe;
point(double _x = 0, double _y = 0)
: x(_x)
, y(_y)
{
}

double len() //向量模长的平方
{
return x * x + y * y;
}
double operator*(const point& i_T) const //点积
{
return x * i_T.x + y * i_T.y;
}
double operator^(const point& i_T) const //叉积
{
return x * i_T.y - y * i_T.x;
}
point operator*(double u) const
{
return point(x * u, y * u);
}
bool operator==(const point& i_T) const
{
return x == i_T.x && y == i_T.y;
}
point operator/(double u) const
{
return point(x / u, y / u);
}
point operator+(const point& i_T)
{
return point(x + i_T.x, y + i_T.y);
}
point operator-(const point& i_T)
{
return point(x - i_T.x, y - i_T.y);
}
friend bool operator<(point a, point b)
{
return fabs(a.y - b.y) < eps ? a.x < b.x : a.y < b.y;
}
void atn2()
{
poe = atan2(y, x);
}
friend ostream& operator<<(ostream& out, point& a)
{
//cout << a.x << ' ' << a.y;
printf("%.0f %.0f", a.x, a.y);
return out;
}
friend istream& operator>>(istream& in, point& a)
{
scanf("%lf%lf", &a.x, &a.y);
return in;
}
};
int bijiao(double x, double y)
{
if (fabs(x - y) < eps)
return 0;
if (x > y)
return 1;
return -1;
}
bool cmp(vec a, vec b)
{
return bijiao(a.poe, b.poe) == 0 ? (a ^ b) >= 0 : a.poe < b.poe;
}
double xuanzhuan(vec a, vec b, vec c) //求三点叉积
{
return (b - a) ^ (c - a);
}
void Andrew(int& tail, point cl[], int n, point ql[]) //求凸包
{
sort(cl + 1, cl + 1 + n);
tail = 1;
ql[1] = cl[1];
for (int i = 2; i <= n; i++) {
while (tail > 1 && xuanzhuan(ql[tail - 1], ql[tail], cl[i]) <= 0)
tail--;
ql[++tail] = cl[i];
}
int basic = tail;
for (int i = n - 1; i >= 1; i--) {
while (tail > basic && xuanzhuan(ql[tail - 1], ql[tail], cl[i]) <= 0)
tail--;
ql[++tail] = cl[i];
}
}
void Minkefusiji(point s[], int& cnt, point pl1[], int tail1, point pl2[], int tail2)
{
s[cnt = 1] = pl1[1] + pl2[1];
for (int i = 1; i <= tail1; i++)
pl1[i] = pl1[i + 1] - pl1[i];
for (int i = 1; i <= tail2; i++)
pl2[i] = pl2[i + 1] - pl2[i];
int a1 = 1, a2 = 1;
while (a1 <= tail1 && a2 <= tail2) {
++cnt;
if ((pl1[a1] ^ pl2[a2]) >= 0)
s[cnt] = s[cnt - 1] + pl1[a1++];
else
s[cnt] = s[cnt - 1] + pl2[a2++];
}
while (a1 <= tail1)
++cnt, s[cnt] = s[cnt - 1] + pl1[a1++];
while (a2 <= tail2)
++cnt, s[cnt] = s[cnt - 1] + pl2[a2++];
}
bool cmp2(point A, point B)
{
return (A ^ B) > 0 || ((A ^ B) == 0 && A.len() < B.len());
}
bool dian_in_tubao(point a, point p[], int tail) //包含边界
{
if ((a ^ p[1]) > 0 || (p[tail] ^ a) > 0)
return false;
int ps = lower_bound(p + 1, p + tail + 1, a, cmp2) - p - 1;
return ((a - p[ps]) ^ (p[ps % tail + 1] - p[ps])) <= 0;
}
point p[MAXN], q2[MAXN], q1[MAXN];
int main()
{
int m, n, q;
cin >> m >> n >> q;
for (int i = 1; i <= m; i++)
cin >> p[i];
int tail1;
Andrew(tail1, p, m, q1);

for (int i = 1; i <= n; i++) {
cin >> p[i];
p[i].x = -p[i].x, p[i].y = -p[i].y;
}
int tail2;
Andrew(tail2, p, n, q2);
tail1--, tail2--;

int cnt, tail;
Minkefusiji(p, cnt, q1, tail1, q2, tail2);

Andrew(tail, p, cnt, q1);
tail--;
point bs = q1[1];
for (int i = 1; i <= tail; i++)
q1[i] = q1[i] - bs;
while (q--) {
point pi;
cin >> pi;
if (dian_in_tubao(pi - bs, q1, tail))
cout << 1 << endl;
else
cout << 0 << endl;
}
return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载