BZPRO
#4132. 四维打击
内存限制:512 MiB
时间限制:100 Sec
提交
提交记录
讨论
题目描述
在一次莫名其妙的意外中,人类舰队成功的掌握了高维打击,并且靠着高维打击打败了三体舰队飞船——“雨滴”。
但是人类由于当时情况紧急,并没有完整的了解高维打击的原理,打击也不是很精确,为了能够掌握每次是否有效的打击到了“雨滴”,我们对模型做如下抽象:
将雨滴当做一个三维空间中由若干个点构成的凸多面体,每次打击坐标为(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的整数,保证数据有梯度;