Convex Polygon - Convex Cut

Time Limit : 1 sec, Memory Limit : 65536 KB

凸多角形の切断


図のように、凸多角形 g を直線 p1p2 で切断し、その左側にできる凸多角形を求め、その面積を出力せよ。

凸多角形 g は隣合う点 pipi+1 (1 ≤ in-1) を結ぶ線が凸多角形 g の辺になるような点の列 p1, p2,..., pn で表される。点 pnp1 を結ぶ線も凸多角形 g の辺となる。

入力

入力は以下の形式で与えられる:

g (the sequence of the points of the polygon)
q (the number of queries = the number of target lines)
1st query
2nd query
:
qth query

g は点の列 p1,..., pn として以下の形式で与えられる:

n
x1 y1 
x2 y2
:
xn yn

1行目の n は点の数を表す。点 pi の座標は2つの整数 xi, yi で与えられる。点は、凸多角形の隣り合った点を反時計回りに訪問するような順番で与えられる。ただし、この問題では、全ての内角の大きさが180度以下であるような多角形を凸多角形とします。

各クエリについて1つの直線が与えられる。直線はそれが通る2つの点 p1, p2 で与えられる。これらの点の座標は4つの整数 p1x, p1y, p2x, p2y で与えられる。

出力

各クエリについて、面積を1行に出力する。出力値は 0.00001 以下の誤差を許容する。

制約

  • 3 ≤ n ≤ 100
  • 1 ≤ q ≤ 100
  • -10000 ≤ xi, yi ≤ 10000
  • -10000 ≤ p1x,p1y,p2x,p2y ≤ 10000
  • 凸多角形の点の座標はすべて異なる
  • p1 と 点p2 は異なる

入力例

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

出力例

2.00000000
4.00000000