四维打击

时间限制:100s      空间限制:512MB

题目描述

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


输入格式

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


输出格式

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


样例输入

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

样例输出

1
0
1

提示

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


题目来源

没有写明来源

Menuappsclose