← 返回题目列表

AtCoder · icpc2013autumn_h

H. 维恩图

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

问题陈述

Alice 是一名私人教师。 她的工作之一是为学生准备学习材料。 现在,作为材料的一部分,她正在绘制两组 $A$ 和 $B$ 之间的维恩图。

维恩图是说明一组或多组之间的关系的图。 例如,两个集合 $A$ 和 $B$ 之间的维恩图如下所示。 该矩形对应于通用集合$U$。 矩形中的两个圆圈分别对应两个集合$A$和$B$。 两个圆的交集对应于两个集合的交集,即 $A \cap B$。

图:两组之间的维恩图

爱丽丝,数学的化身,想出了一个特殊的条件,让她的维恩图更加美丽。 她的条件是维恩图每个部分的面积等于其对应集合中元素的数量。 换句话说,一个圆的面积必须等于 $|A|$,另一个圆的面积必须等于 $|B|$,它们的交集必须有等于 $|A \cap B|$ 的面积。这里,$|X|$ 表示集合$X$ 中的元素数量。

Alice 已经画了一个矩形,但一直很难弄清楚在哪里画其余的两个圆圈,因为她甚至无法忍受人类会犯的小错误。 作为爱丽丝的老朋友,你的任务是帮助她编写一个程序来确定两个圆的圆心和半径,使它们满足上述条件。


输入

输入是数据集序列。 数据集数量不超过 300 美元。

每个数据集的格式如下。

$U_W$ $U_H$ $|A|$ $|B|$ $|A \cap B|$

前两个整数 $U_W$ 和 $U_H$ ($1 \le U_W, U_H \le 100$) 分别表示对应通用集合 $U$ 的矩形的宽度和高度。 接下来的三个整数 $|A|$、$|B|$ 和 $|A \cap B|$ ($1 \le |A|, |B| \le 10{,}000$ 和 $0 \le |A \cap B| \le \min\{|A|,|B|\}$) 分别表示集合 $A$、$B$ 和 $A \cap B$ 的元素数量。 输入以五个零终止。

你可以假设,即使$U_W$和$U_H$在$\pm 0.01$范围内变化,在Alice条件下是否可以画两个圆也不会改变。

输出

对于每个数据集,输出满足爱丽丝条件的两个圆的圆心和半径,如下所示:

$X_A$ $Y_A$ $R_A$ $X_B$ $Y_B$ $R_B$

$X_A$ 和$Y_A$ 是对应于集合$A$ 的圆心坐标。 $R_A$ 是对应于集合$A$ 的圆的半径。 $X_B$、$Y_B$ 和 $R_B$ 是集合 B 的值。 这些值必须用空格分隔。

如果不可能满足条件,则输出:

不可能

每个部分的面积绝对误差不得大于 $0.0001$。 此外,两个圆圈必须位于矩形内,且误差范围为 $0.0001$,或者更准确地说,必须满足以下所有四个条件:

  • $X_A - R_A \ge -0.0001$

  • $X_A + R_A \le U_W + 0.0001$

  • $Y_A - R_A \ge -0.0001$

  • $Y_A + R_A \le U_H + 0.0001$

$X_B$、$Y_B$ 和 $R_B$ 必须满足相同的条件。


示例输入

10 5 1 1 0
10 5 2 2 1
10 10 70 70 20
0 0 0 0 0

样本输入的输出

1 1 0.564189584 3 1 0.564189584
1 1 0.797884561 1.644647246 1 0.797884561
impossible