Sign of Friendship

AtCoder

IDzone2021_b

Time2000ms

Memory256MB

Difficulty—

You are now standing under a very high tower, of height $1000$. At a position whose distance from the tower is $D$, there is a UFO up in the sky at height $H$ (see the figure at Sample Input / Output 1), and you want to send it a radio wave. There are $N$ obstacles between the tower and the UFO. The $i$\-th obstacle stands at the position $d_i$ meters from the tower towards the UFO, and has a height of $h_i$. You want to climb up the tower so that no obstacle crosses the line between you and the UFO. Find the minimum height you need to climb. We assume that the ground is a flat plane, and the towers and obstacles stand vertically from the ground. Additionally, if the top of an obstacle lies exactly on the line connecting you and the UFO, we assume that the obstacle does not cross that line. ## Constraints * All values in input are integers. * $1 ≤ N ≤ 100$ * $1 ≤ d_i < D ≤ 1000$ * $1 ≤ h_i < H ≤ 1000$ ## Input Input is given from Standard Input in the following format: $N$ $D$ $H$ $d_1$ $h_1$ $d_2$ $h_2$ $\vdots$ $d_N$ $h_N$ [samples]

Samples

Input #1

1 10 10
3 5

Output #1

2.857142857142857

If you climb the tower to the height of $\frac{20}{7}$, no obstacle will cross the line between you and the UFO, as shown below.
![image](https://img.atcoder.jp/ghi/425da28ab0802405a8541ed16d81e5cf.png)

Input #2

1 10 10
3 2

Output #2

0.0

You can send a radio wave to the UFO without climbing up the tower.

Input #3

Output #3

245.3080684596577

API Response (JSON)

{
  "problem": {
    "name": "Sign of Friendship",
    "description": {
      "content": "You are now standing under a very high tower, of height $1000$. At a position whose distance from the tower is $D$, there is a UFO up in the sky at height $H$ (see the figure at Sample Input / Output ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "zone2021_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are now standing under a very high tower, of height $1000$. At a position whose distance from the tower is $D$, there is a UFO up in the sky at height $H$ (see the figure at Sample Input / Output ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments