Vongress

Time Limit : 2 sec, Memory Limit : 131072 KB

太郎君は Vongress と呼ばれるゲームが大好きである.Vongress とは,n 頂点からなる凸多角形である盤の上で行われる陣取りゲームである.

このゲームでは,m 人のプレイヤーが,盤の内側にそれぞれ 1 つ駒を置く.駒の位置は x座標と y 座標の組で表され,駒の大きさは考えない.

あるプレイヤーの陣地とは,盤上でその人が置いた駒が最も近くにあるような場所からなる領域である.プレイヤーは,自分の陣地の面積をスコアとして得る.

太郎君はいつも盤の形状,置かれた駒の位置,各プレイヤーのスコアを記録していたが,ある日うっかり駒の位置を記録するのを忘れてしまった.そこで太郎君は,盤の形状とプレイヤーの得点から,矛盾のない駒の位置を書き加えることにした.

あなたの仕事は,太郎君に代わって各プレイヤーの得点と矛盾しない駒の位置を求めることである.

Input

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

n m
x1 y1
x2 y2
:
xn yn
r1
r2
:
rm

n は盤である凸多角形の頂点数,m はプレイヤーの数を表す.(xi, yi) は盤の頂点の座標を表す.r1, . . . , rm は各プレイヤーが得たスコアの比を表す.

Constraints

  • 3 ≤ n ≤ 100
  • 1 ≤ m ≤ 100
  • −104xi, yi ≤ 104
  • 1 ≤ rj ≤ 100
  • 入力は全て整数である.
  • 凸多角形の頂点 (xi, yi) は反時計回りの順番で与えられる.

Output

m 個の駒の位置を以下の形式で出力せよ.

x'1 y'1
x'2 y'2
:
x'm y'm

(x'k, y'k) は,k 番目のプレイヤーの駒の位置である.

出力は次の条件を満たさなければならない.

  • 駒が凸多角形の内側にある.境界線上にあってもよい.
  • どの 2 つの駒も 10−5 以上距離が離れている.
  • 与えられる凸多角形の面積を S とする.出力から求まる k 番目のプレイヤーの陣地の面積について, $\frac{r_k}{r_1+...+r_m} S$ との絶対誤差または相対誤差が 10−3 未満である.

Sample Input 1

4 5
1 1
-1 1
-1 -1
1 -1
1
1
1
1
1

Output for the Sample Input 1

0.0000000000 0.0000000000
0.6324555320 0.6324555320
-0.6324555320 0.6324555320
-0.6324555320 -0.6324555320
0.6324555320 -0.6324555320

下図のように駒を配置すれば,全プレイヤーが同じスコアを得られる.黒い線分が盤,赤い点がプレイヤーの駒,青い線分がプレイヤーの陣地の境界線をそれぞれ表す.

Vongress

Sample Input 2

4 3
1 1
-1 1
-1 -1
1 -1
9
14
9

Output for the Sample Input 2

-0.5 -0.5
0 0
0.5 0.5

下図のように駒を配置すればよい.

Vongress

Sample Input 3

8 5
2 0
1 2
-1 2
-2 1
-2 -1
0 -2
1 -2
2 -1
3
6
9
3
5

Output for the Sample Input 3

1.7320508076 -0.5291502622
1.4708497378 -0.2679491924
-0.4827258592 0.2204447068
-0.7795552932 0.5172741408
-1.0531143674 0.9276127521

下図のように駒を配置すればよい.

Vongress

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 4, Tokyo, Japan, 2014-09-15
http://acm-icpc.aitea.net/
http://jag2014summer-day4.contest.atcoder.jp/