Sgu345 凸包切割

时间限制:10s      空间限制:162MB

题目描述

给你凸包上的N个点(保证是很普通的凸包)。给你M条直线,每次询问你这条直线把凸包切成的两部分中,较小的一部分的面积。如果这条直线没把凸包切成两部分,则输出0。 输入文件: 第一行一个数N。如题所述。(n<=100000) 接下来N行,每行两个实数,表示一个凸包上的点的坐标。 一个数M。如题所述。(m<=100000) 接下来M行,每行4个实数x1,y1,x2,y2,描述一条经过(x1,y1),(x2,y2)的直线。


输入格式

M行,对于每条直线


输出格式

给出询问的答案,保留6位小数。


样例输入

4
0 0
1 1
0 1
1 0
2
-1 -1 2 2
0.5 -1 0.5 1


样例输出

0.500000
0.500000


提示

没有写明提示


题目来源

没有写明来源