← 返回题目列表

AtCoder · icpc2014summer_day4_j

J. 冯内斯

中文机器翻译题面 查看原题

问题陈述

太郎君非常喜欢一款叫做Vongress的游戏。Vongress是在一个由 $n$ 个顶点组成的凸多边形棋盘上进行的占点游戏。

在这个游戏中,$m$ 名玩家会在棋盘的内部各放置一个棋子。 棋子的位置用 $x$ 坐标和 $y$ 坐标的组合表示,不考虑棋子的大小。

一名玩家的阵地是由棋盘上那些距离该玩家放置的棋子最近的地方组成的区域。 玩家以自己阵地的面积作为得分。

太郎君总是记录棋盘的形状、放置的棋子的位置以及各玩家的得分, 但有一天他不小心忘记记录棋子的位置。 因此,太郎君决定根据棋盘的形状和玩家的得分,添加一个与已有信息不矛盾的棋子位置。

你的任务是代替太郎君,求出一个与各玩家得分不矛盾的棋子位置。


输入

输入按以下格式给出。

$n$ $m$
$x_1$ $y_1$
$x_2$ $y_2$
:
:
$x_n$ $y_n$
$r_1$
$r_2$
:
:
$r_m$

$n$ 是该圆盘的凸多边形的边数,$m$ 表示猎物数量。 $(x_i,y_i)$ 表示盘上游的坐标。 $r_1,\ldots,r_m$ 表示每个猎物获得的 su 核心的比例。 所有输入

约束

  • $3\le n \le 100$
  • $1\le m \le 100$
  • $-10^4 \le x_i,y_i \le 10^4$
  • $1\le r_j \le 100$
  • 都是整数。
  • 凸多边形 $(x_i,y_i)$ 的顶点按反时针方向排列。

输出

输出$m$棋子的位置,格式如下。

$x'_1$ $y'_1$
$x'_2$ $y'_2$
:
:
$x'_m$ $y'_m$

$(x'_k,y'_k)$ 是该棋子在第$k个猎物中的位置。

输出必须满足以下条件。

  • 凸多边形中间的边界,棋子所在的位置。它可能在直线上。
  • 两匹马之间的差距超过10^{-5}$。
  • 设给定凸多边形的面积为$S$。 关于从输出获得的第$k次猎物场面积, $\frac{r_k}{r_1+\cdots+r_m}S$之间的绝对或相对间隙小于$10^{-3}$。

示例输入 1

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

样本输入 1 的输出

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

如果像下图那样布置棋子,那么所有玩家都可以获得相同的分数。黑色线段表示棋盘,红色点表示玩家的棋子,蓝色线段分别表示玩家的阵地边界线。


示例输入 2

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

样本输入 2 的输出

-0.5 -0.5
0 0
0.5 0.5

按下图摆放棋子就可以了。


示例输入 3

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

样本输入 3 的输出

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

按下图摆放棋子就可以了。