C. Help Greg the Dwarf

Codeforces

IDCF98C

Time2000ms

Memory256MB

Difficulty—

geometryternary 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).

在遥远的王国里住着一位非常奇特的居民——矮人格拉库拉。然而，他奇特的名字并不是最奇怪的事情（毕竟，大家早就习惯直接叫他矮人格雷格了）。真正特别的是矮人格雷格——他已经活了200多年；此外，他住在一座被废弃的墓地的墓穴里，从来没人见过他在白天外出。更没有人见过格雷格买过任何食物。因此，当地狱龙悲剧性死亡后，牲畜仍持续从田地中消失时，没有人感到特别惊讶。 neighborhood 的居民早就确信，那头无害的龙从未对牲畜失踪负责（考虑到龙一直真诚地坚持其素食主义观点）。但这一切还不是故事中最糟糕的部分。最糟糕的部分是：就在几分钟前，矮人格雷格以某种难以理解的方式进入了你的房子，并请求你帮助他解决一个问题。问题是：不久前，格雷格决定订购一口新棺材（了解他的怪异性格，你对此毫不惊讶）。但问题是：一条非常长的、双向的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]。所有 Hack 数据也将满足该条件。在第一个示例中，答案受棺材长度限制（记住——棺材的宽度不应大于其长度）。在第二个示例中，由于旋转轮子的存在，可以将棺材拖过走廊：首先，沿一侧向前拖动，直到不会被墙壁阻碍；然后，垂直于初始移动方向，沿相邻侧向前移动（记住——棺材的任意移动和旋转都是允许的）。 ## 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]。所有 Hack 数据也将满足该条件。 [samples] ## Note 在第一个示例中，答案受棺材长度限制（记住——棺材的宽度不应大于其长度）。在第二个示例中，由于旋转轮子的存在，可以将棺材拖过走廊：首先，沿一侧向前拖动，直到不会被墙壁阻碍；然后，垂直于初始移动方向，沿相邻侧向前移动（记住——棺材的任意移动和旋转都是允许的）。

**Definitions** Let $ a, b, l \in \mathbb{R}^+ $ be given constants with $ a, b \geq 1 $, $ l \geq 1 $, representing the widths of the two corridor segments and the length of the rectangular coffin, respectively. Let $ w \in \mathbb{R}^+ $ be the width of the coffin, with $ w \leq l $. **Constraints** 1. $ 1 \leq a, b, l \leq 10^4 $ 2. $ 0 < w \leq l $ **Objective** Find the maximum $ w \in \mathbb{R}^+ $ such that a rectangle of dimensions $ l \times w $ can be maneuvered around a right-angled corner connecting two perpendicular corridors of widths $ a $ and $ b $, under arbitrary continuous rotations and translations in the plane. The coffin fits if and only if there exists an angle $ \theta \in \left(0, \frac{\pi}{2}\right) $ such that: $$ \frac{w}{\sin \theta} + \frac{l}{\cos \theta} \leq a \quad \text{and} \quad \frac{w}{\cos \theta} + \frac{l}{\sin \theta} \leq b $$ Equivalently, the maximal $ w $ is the supremum of values satisfying: $$ w \leq \min\left( a \sin \theta - l \cos \theta,\; b \cos \theta - l \sin \theta \right) \quad \text{for some } \theta \in \left(0, \frac{\pi}{2}\right) $$ with the constraint that both expressions on the right are non-negative. 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": "C. 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": "CF98C"
  },
  "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": "在遥远的王国里住着一位非常奇特的居民——矮人格拉库拉。然而，他奇特的名字并不是最奇怪的事情（毕竟，大家早就习惯直接叫他矮人格雷格了）。真正特别的是矮人格雷格——他已经活了200多年；此外，他住在一座被废弃的墓地的墓穴里，从来没人见过他在白天外出。更没有人见过格雷格买过任何食物。因此，当地狱龙悲剧性死亡后，牲畜仍持续从田地中消失时，没有人感到特别惊讶。 neighborhood 的居民早就确信，那头...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, l \\in \\mathbb{R}^+ $ be given constants with $ a, b \\geq 1 $, $ l \\geq 1 $, representing the widths of the two corridor segments and the length of the rectangular coffin,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments