UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4132. 四维打击

统计 下载数据

Description

在一次莫名其妙的意外中,人类舰队成功的掌握了高维打击,并且靠着高维打击打败了三体舰队飞船——“雨滴”。
但是人类由于当时情况紧急,并没有完整的了解高维打击的原理,打击也不是很精确,为了能够掌握每次是否有效的打击到了“雨滴”,我们对模型做如下抽象:
将雨滴当做一个三维空间中由若干个点构成的凸多面体,每次打击坐标为(x,y,z),如果这个点在凸多面体的内部或者表面,则认为这次打击是成功的,现在给你若干个打击坐标,要求你计算打击是否成功。

Input

输入的第一行包含一个整数N,表示凸多面体由这N个点构成,不保证这N个点都在凸多面体的表面。
接下来N行,每行三个整数 (x,y,z),代表点的xyz坐标。
接下来一行一个整数M,代表M次打击询问。
接下来M行,每行三个整数(x,y,z),代表打击点的xyz坐标。

Output

对于每组询问,打击成功输出1,打击失败输出0

Sample Input

1
4
0 0 0
2 0 0
0 2 0
0 0 2
3
0 0 0
2 2 2
0 1 0

Sample Output

1
0
1

Hint

对于100%的测试数据,n ≤ 50000,m ≤ 100000,所有坐标都是绝对值不超过104的整数,保证数据有梯度;


Source