014 - 真夏の夜の夢

writerは幾何が苦手なので、問題やテストケースに不備があるかもしれません。
問題文がゴミクズでわかりにくいので、意味不明な文章があったら教えてください。

問題

森があります。
この森はたいそう不思議な森でありました。
木が1距離単位間隔に並んでいたのです。
そこには妖精たちが住んでいたのでございます。
妖精たちの国にはオベーロンという名の妖精王と、ティターニアという女王がいらっしゃいました。
しかしながら御二方は「とりかえ子」を巡って喧嘩をなさっていました。
その様子をご覧になった妖精の賢者はそれを解決するために次のようなことを提案されました。

• オベーロンは国の重要な部分を今まで通り統治する。
• ティターニアは国の運営に運営に関わらない箇所を分割統治する。

これを満たすように地図を策定したところ、ティターニアの統治する領土は、オベーロンの統治する領土に完全に含まれる、N個の木を頂点とする多角形になった。
しかし重要な部分をオベーロンが統治することになったため、M個の穴があいてしまった。
この部分も多角形で、頂点は全て木を頂点としていて、あるオベーロンが統治する部分とそれ以外のオベーロンが統治する部分は繋がっていない。
各頂点の木の座標が与えられるので、ティターニアが統治する面積を求めよ。
なお、頂点_iは頂点_i+1と繋がっている。
このとき、頂点_Nは頂点₁とつながっている。
その後ティターニアの統治する領土に含まれる木の数Fが与えられる。
領土内の木を維持するにはコストがかかってしまう。
なお、ティターニアが統治する領土と、ティターニアが統治する領土の内部にあるオベーロンが統治する領土のちょうど境界線にある木はオベーロンが管理するため、そのコストは考えない。F本の木のうちその木の本数はf本である。
かかるコストはティターニアが管理する木の本数×(穴の数+1)である。
それも求めよ。

入力

N M
x1 y1
......
xN yN
F

x, yは最も南西にある木を基準とした距離単位で与えられる。

出力

S
C

面積とコストをそれぞれ改行して出力せよ。

制約

$1$ ≤ $N$ ≤ $10$⁶
$0$ ≤ $x$, $y$ ≤ $10$⁶
$0$ ≤ $f$ < $F$ ≤ $10$⁶

テストケース

例1

入力

4 0
0 0
2 0
2 2
0 2
9
0

出力

4
9

これは一辺が2の正方形である。

例2

入力

4 1
0 0
3 0
3 3
0 3
16
4

出力

8
24

これは一辺が3の正方形の内部に、一辺が1の正方形の形をした穴が空いていることになる。
よって面積は3*3-1*1=8である。

私はシェイクスピアとメンデルスゾーンが好きです。