UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2585. 世纪大战

统计 下载数据

Description

      HL的暴政统治始终是不得人心。世界上的最大强权——HG帝国,以推翻暴政弘扬民主为由(其实是看中了窘国国内丰富的花生油资源),对窘国发动了全面战争。在地面部队入侵之前,HG国为主的多国部队对窘国进行了疯狂轰炸。
窘国总共有N个城市,我们可以认为窘国的国土是能包含这N个城市的周长最小的多边形(好绕口阿K)。现在窘国遭到了HG帝国的不断轰炸,HG使用的炸弹非常先进,它的杀伤范围是一个巨大的三角形!
HL那家伙早就和ZS一起躲到了他新修的地下宫殿里去享福去了,而把战斗的指挥权全部交给你。(算他有自知之明,以HL的即时战略技术,就算练习10000年还是打不过HG)你现在的首要问题是针对HG的轰炸进行反击,而在组织反击之前,你先要搞清楚每次轰炸究竟损失有多大。也就是要搞清楚,每次轰炸的杀伤范围内,有多大的面积是窘国的国土。

Input

第一行一个整数N。
以下N行,每行两个实数Xi,Yi,表示一个城市的坐标。
紧接着一行有一个整数M,表示进行了多少轮轰炸。
然后是M行,每行有6个实数X1i,Y1i,X2i,Y2i,X3i,Y3i。表示这次轰炸投放的炸弹的杀伤范围是以(X1i,Y1i)、(X2i,Y2i)、(X3i,Y3i)为顶点的三角形。(输入的实数,小数点后最多有4位)

Output

    共M行,每行输出相应的轮次中,杀伤范围内的窘国国土面积。输出保留三位小数。若对于每个输出的面积,与标准程序答案相差不超过2,即算正确。

Sample Input

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

Sample Output

1

【数据范围】
N,M<=100000,坐标范围在100000以内。友情提示:请小心处理精度。

Hint

暂无SPJ,请不要提交!

Source