[ICPC 2020 Nanjing R] Interested in Skiing

Luogu

IDLGP9630

Time1000ms

Memory256MB

DifficultyP6

计算几何2020Special JudgeO2优化ICPC南京

Kotori is interested in skiing. The skiing field is an infinite strip going along $y$-axis on the 2-dimensional plane where all points $(x, y)$ in the field satisfies $-m \le x \le m$. When skiing, Kotori cannot move out of the field, which means that the absolute value of his $x$-coordinate should always be no more than $m$. There are also $n$ segments on the ground which are the obstacles and Kotori cannot move across the obstacles either. Kotori will start skiing from $(0, -10^{10^{10^{10^{10}}}})$ (you can regard this $y$-coordinate as a negative infinity) and moves towards the positive direction of the $y$-axis. Her vertical (parallel to the $y$-axis) speed is always $v_y$ which cannot be changed, however she can control her horizontal (parallel to the $x$-axis) speed in the interval of $[-v_x, v_x]$. The time that Kotori changes her velocity can be neglected. Your task is to help Kotori calculate the minimum value of $v_x^*$ that once $v_x>v_x^*$ she can safely ski through the skiing field without running into the obstacles. ## Input There is only one test case in each test file. The first line of the input contains three positive integers $n$, $m$ and $v_y$ ($1 \le n \le 100$, $1 \le m \le 10^4$, $1 \le v_y \le 10$), indicating the number of obstacles, the half width of the skiing field and the vertical speed. For the following $n$ lines, the $i$-th line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($-m \le x_1, x_2 \le m$, $-10^4 \le y_1, y_2 \le 10^4$, $x_1 \ne x_2$ or $y_1 \ne y_2$) indicating the $i$-th obstacle which is a segment connecting point $(x_1, y_1)$ and $(x_2, y_2)$, both inclusive (that is to say, these two points are also parts of the obstacle and cannot be touched). It's guaranteed that no two obstacles intersect with each other. ## Output Output one line containing one number indicating the minimum value of $v_x^*$. If it is impossible for Kotori to pass through the skiing field, output ``-1`` (without quotes) instead. Your answer will be considered correct if and only if its absolute or relative error does not exceed $10^{-6}$. [samples]

Samples

Input #1

Output #1

1.000000000000000

Input #2

2 1 2
-1 0 1 0
1 1 0 1

Output #2

-1

Input #3

2 3 7
-3 0 2 2
3 1 -2 17

Output #3

1.866666666666666

Input #4

1 100 1
-100 0 99 0

Output #4

0.000000000000000

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2020 Nanjing R] Interested in Skiing",
    "description": {
      "content": "Kotori is interested in skiing. The skiing field is an infinite strip going along $y$-axis on the 2-dimensional plane where all points $(x, y)$ in the field satisfies $-m \\le x \\le m$. When skiing, Ko",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9630"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kotori is interested in skiing. The skiing field is an infinite strip going along $y$-axis on the 2-dimensional plane where all points $(x, y)$ in the field satisfies $-m \\le x \\le m$. When skiing, Ko...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments