E. Help Greg the Dwarf

Codeforces

IDCF99E

Time2000ms

Memory256MB

Difficulty—

binary searchgeometryternary search

English · Original

Chinese · Translation

Formal · Original

A very unusual citizen lives in a far away kingdom — Dwarf Gracula. However, his unusual name is not the weirdest thing (besides, everyone long ago got used to calling him simply Dwarf Greg). What is special about Dwarf Greg — he's been living for over 200 years; besides, he lives in a crypt on an abandoned cemetery and nobody has ever seen him out in daytime. Moreover, nobody has ever seen Greg buy himself any food. That's why nobody got particularly surprised when after the infernal dragon's tragic death cattle continued to disappear from fields. The people in the neighborhood were long sure that the harmless dragon was never responsible for disappearing cattle (considering that the dragon used to be sincere about his vegetarian views). But even that's not the worst part of the whole story. The worst part is that merely several minutes ago Dwarf Greg in some unintelligible way got inside your house and asked you to help him solve a problem. The point is that a short time ago Greg decided to order a new coffin (knowing his peculiar character, you are not surprised at all). But the problem is: a very long in both directions L-shaped corridor leads to Greg's crypt, and you can't drag just any coffin through that corridor. That's why he asked you to help. <center>![image](https://espresso.codeforces.com/2e4cb52322e908a0f4a12a011c7b3e43774cc3ea.png)</center>You've formalized the task on a plane like this: let the corridor's width before and after the turn be equal to _a_ and _b_ correspondingly (see the picture). The corridor turns directly at a right angle, the coffin is a rectangle whose length and width are equal to _l_ and _w_ (_l_ ≥ _w_) correspondingly. Dwarf Greg has already determined the coffin's length (_l_), which is based on his height; your task is to determine the coffin's maximally possible width (_w_), at which it can be brought to the crypt. Besides, due to its large mass (pure marble!) the coffin is equipped with rotating wheels; therefore it is impossible to lift it off the ground, however, arbitrary moves and rotations of the coffin in the plane become possible. The coffin may be rotated arbitrarily just before you drag it into crypt and move through the corridor. Greg promised that if you help him, he will grant you immortality (I wonder how?). And if you don't, well... trust me, you don't want to know what happens if you don't help him... ## Input The first line contains three space-separated integers _a_, _b_ and _l_ from the problem's statement (1 ≤ _a_, _b_, _l_ ≤ 104). ## Output Print the maximally possible width of a coffin with absolute or relative error no more than 10 - 7. If a coffin with the given length and positive width (the coffin that would meet the conditions from the problem's statement) does not exist, print "_My poor head =(_" (without quotes). It is guaranteed that if the answer is positive, it will be not less than 10 - 7. All the hacks will also be checked to meet that condition. [samples] ## Note In the first example the answer is restricted by the coffin's length (remember — coffin's widths should not be larger than it's length). In the second example it is possible to drag the coffin through the corridor thanks to rotating wheels: firstly, drag it forward by one side while it will not be hampered by the wall, then move it forward by adjacent side perpendicularly to the initial movement direction (remember — arbitrary moves and rotations of the coffin are possible).

在遥远的王国里住着一位非常奇特的居民——矮人格拉库拉。然而，他奇特的名字并不是最奇怪的（况且，大家都早已习惯直接叫他矮人格雷格）。矮人格雷格的特别之处在于：他已经活了两百多年；此外，他住在一座被废弃的墓地的墓穴中，从没有人见过他在白天外出。更没人见过格雷格买过任何食物。因此，当地狱龙悲剧性死亡后，田地里的牛仍持续失踪时，没有人感到特别惊讶。邻居们早就确信，那头无害的龙从未对牛的失踪负责（毕竟，龙一直真诚地坚持素食主义）。但这些还不是整个故事中最糟糕的部分。最糟糕的部分是：就在几分钟前，矮人格雷格以某种难以理解的方式进入了你的家，并请求你帮他解决一个问题。事情是这样的：不久前，格雷格决定订购一口新棺材（考虑到他奇特的性格，你对此毫不惊讶）。但问题在于：通往格雷格墓穴的是一条在两个方向上都非常长的L形走廊，你无法将任意棺材通过这条走廊。因此，他请你帮忙。你将这个问题在平面上形式化如下：设转弯前和转弯后的走廊宽度分别为 #cf_span[a] 和 #cf_span[b]（见图）。走廊在直角处直接转弯，棺材是一个长宽分别为 #cf_span[l] 和 #cf_span[w]（#cf_span[l ≥ w]）的矩形。矮人格雷格已经确定了棺材的长度（#cf_span[l]），这基于他的身高；你的任务是确定在能够被运送到墓穴的前提下，棺材可能的最大宽度（#cf_span[w]）。此外，由于棺材质量巨大（纯大理石！），它配备了旋转轮子；因此不可能将它抬离地面，但棺材在平面上可以进行任意移动和旋转。你可以在将棺材拖入墓穴并穿过走廊之前，对其进行任意旋转。格雷格承诺，如果你帮他，他将赐予你永生（我不知道这怎么可能）。而如果你不帮……相信我，你并不想知道不帮他的后果…… 第一行包含问题陈述中的三个空格分隔的整数 #cf_span[a]、#cf_span[b] 和 #cf_span[l]（#cf_span[1 ≤ a, b, l ≤ 104]）。请输出棺材可能的最大宽度，绝对或相对误差不超过 #cf_span[10 - 7]。如果不存在满足题目条件的、给定长度且宽度为正的棺材，请输出 "_My poor head =(_"（不含引号）。保证若答案为正，则其值不小于 #cf_span[10 - 7]。所有测试数据也将满足该条件。在第一个示例中，答案受棺材长度限制（记住——棺材的宽度不应超过其长度）。在第二个示例中，得益于旋转轮子，棺材可以通过走廊：首先，沿一边向前拖动，直到它不再被墙壁阻挡；然后，沿相邻边垂直于初始移动方向向前移动（记住——棺材可以进行任意移动和旋转）。 ## Input 第一行包含问题陈述中的三个空格分隔的整数 #cf_span[a]、#cf_span[b] 和 #cf_span[l]（#cf_span[1 ≤ a, b, l ≤ 104]）。 ## Output 请输出棺材可能的最大宽度，绝对或相对误差不超过 #cf_span[10 - 7]。如果不存在满足题目条件的、给定长度且宽度为正的棺材，请输出 "_My poor head =(_"（不含引号）。保证若答案为正，则其值不小于 #cf_span[10 - 7]。所有测试数据也将满足该条件。 [samples] ## Note 在第一个示例中，答案受棺材长度限制（记住——棺材的宽度不应超过其长度）。在第二个示例中，得益于旋转轮子，棺材可以通过走廊：首先，沿一边向前拖动，直到它不再被墙壁阻挡；然后，沿相邻边垂直于初始移动方向向前移动（记住——棺材可以进行任意移动和旋转）。

**Definitions** Let $ a, b, l \in \mathbb{R}^+ $ be given constants with $ a, b, l \geq 1 $ and $ l \geq w $, where $ w $ is the unknown width of the rectangular coffin. **Constraints** The coffin (a rectangle of length $ l $ and width $ w \leq l $) must be maneuverable through an L-shaped corridor with perpendicular arms of widths $ a $ and $ b $, respectively. The coffin may be translated and rotated arbitrarily in the plane, but must remain entirely within the corridor at all times. **Objective** Find the maximum $ w \in (0, l] $ such that the rectangle $ l \times w $ can pass through the L-shaped corridor. If no such positive $ w $ exists, output "_My poor head =(_". The maximal $ w $ satisfies: $$ \min_{\theta \in [0, \pi/2]} \left( \frac{a}{\sin \theta} + \frac{b}{\cos \theta} \right) \geq l $$ and the maximal feasible $ w $ is: $$ w = \max \left\{ w' \in (0, l] \,\middle|\, \min_{\theta \in [0, \pi/2]} \left( \frac{a - w' \cos \theta}{\sin \theta} + \frac{b - w' \sin \theta}{\cos \theta} \right) \geq 0 \right\} $$ Equivalently, solve for the largest $ w \in (0, l] $ such that: $$ \min_{\theta \in (0, \pi/2)} \left( \frac{a}{\sin \theta} + \frac{b}{\cos \theta} - w \left( \cot \theta + \tan \theta \right) \right) \geq 0 $$ If no such $ w > 0 $ exists, output "_My poor head =(_".

Samples

Input #1

2 2 1

Output #1

1.0000000

Input #2

2 2 2

Output #2

2.0000000

Input #3

2 2 3

Output #3

1.3284271

Input #4

2 2 6

Output #4

My poor head =(

API Response (JSON)

{
  "problem": {
    "name": "E. Help Greg the Dwarf",
    "description": {
      "content": "A very unusual citizen lives in a far away kingdom — Dwarf Gracula. However, his unusual name is not the weirdest thing (besides, everyone long ago got used to calling him simply Dwarf Greg). What is ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF99E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A very unusual citizen lives in a far away kingdom — Dwarf Gracula. However, his unusual name is not the weirdest thing (besides, everyone long ago got used to calling him simply Dwarf Greg). What is ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在遥远的王国里住着一位非常奇特的居民——矮人格拉库拉。然而，他奇特的名字并不是最奇怪的（况且，大家都早已习惯直接叫他矮人格雷格）。矮人格雷格的特别之处在于：他已经活了两百多年；此外，他住在一座被废弃的墓地的墓穴中，从没有人见过他在白天外出。更没人见过格雷格买过任何食物。因此，当地狱龙悲剧性死亡后，田地里的牛仍持续失踪时，没有人感到特别惊讶。邻居们早就确信，那头无害的龙从未对牛的失踪负责（毕竟，龙一...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, l \\in \\mathbb{R}^+ $ be given constants with $ a, b, l \\geq 1 $ and $ l \\geq w $, where $ w $ is the unknown width of the rectangular coffin.  \n\n**Constraints**  \nThe cof...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments