問題一覧 > 通常問題

No.2376 Obstacle Competitive Programming

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 52
作問者 : Michirakara / テスター : KowerKoint2010 hibit_at 👑 seekworser poyon
お気に入りにしたユーザー ProblemId : 9319 / 自分の提出
問題文最終更新日: 2023-08-15 09:14:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 396 (Asakatsu Presents 2) (順位表) の他の問題:

Problem Statement

Story

To help competitive programmers get more exercise, hibit has decided to hold an event with novel rules: "Obstacle Competitive Programming".
Obstacle Competitive Programming is held in a forest where many logs have been placed.
Each participant runs from their starting point to their own computer without touching any log, and then starts competitive programming.


There are $N$ logs in the forest, and the $i\ (1\leq i\leq N)$-th log is represented as a line segment from point $(x_{i,1},y_{i,1})$ to point $(x_{i,2},y_{i,2})$ on the coordinate plane.
Here, it is guaranteed that the coordinates of all endpoints of the logs are distinct, and that no endpoint of a log lies on another log.
There are also $M$ participants. The $j\ (1\leq j\leq M)$-th participant starts at the coordinates $(x_{a_j,b_j},y_{a_j,b_j})$, which is an endpoint of a log, and runs to the coordinates $(x_{c_j,d_j},y_{c_j,d_j})$, which is an endpoint of another log and where their computer is placed, in such a way that the route has no common point with any log, except for its start and end points.

Since all the participants are competitive programmers, they want to reach their computers by as short a distance as possible.
For each participant, it can be said that the lengths of all possible routes cannot be made smaller than some real number $x$.
Output the largest possible such real number $x$.(The problem statement was corrected on 2023/08/15.)

Input

$N\ M$
$x_{1,1}\ y_{1,1}\ x_{1,2}\ y_{1,2}$
$x_{2,1}\ y_{2,1}\ x_{2,2}\ y_{2,2}$
$\vdots$
$x_{N,1}\ y_{N,1}\ x_{N,2}\ y_{N,2}$
$a_1\ b_1\ c_1\ d_1$
$a_2\ b_2\ c_2\ d_2$
$\vdots$
$a_M\ b_M\ c_M\ d_M$

  • $2\leq N\leq 150$
  • $1\leq M\leq 2\times 10^5$
  • $-10^4\leq x_{i,j}\leq 10^4\ (1\leq i\leq N, j\in \{1,2\})$
  • $-10^4\leq y_{i,j}\leq 10^4\ (1\leq i\leq N, j\in \{1,2\})$
  • $(x_{i,j},y_{i,j})\neq(x_{k,l},y_{k,l})\ (1\leq i< k\leq N, j\in \{1,2\}, l\in \{1,2\})$
  • $(x_{i,1},y_{i,1})\neq(x_{i,2},y_{i,2})(1\leq i\leq N)$
  • $a_i\neq c_i\ (1\leq i\leq M)$
  • $1\leq a_i,c_i \leq N\ (1\leq i\leq M)$
  • $b_i\in \{1,2\}\ (1\leq i\leq M)$
  • $d_i\in \{1,2\}\ (1\leq i\leq M)$
  • All input values are integers
  • It is guaranteed that no endpoint of a log lies on another log
  • It is guaranteed that every participant can reach their computer

Output

Output $M$ lines. On the $j\ (1\leq j \leq M)$-th line, output the distance from the $j$-th participant's starting position to their computer, as a decimal or an integer.
Your answer is judged correct if its absolute or relative error from the exact answer is at most $10^{-5}$.

Sample

Sample 1
Input
2 1
0 1 0 2
1 2 2 3
1 1 2 2
Output
2.828427124746190097603377448


The route is as shown here.
In this case, it is optimal to move in a straight line from point $(0, 1)$ to point $(2, 3)$, and the distance traveled is $2\sqrt{2}≒2.8284271$. This route comes arbitrarily close to log $2$ along the way, but by shifting the route slightly to the left or right, it can be made to have no common point with log $2$.

Sample 2
Input
3 2
-1 1 2 0
0 0 2 2
0 2 3 0
1 1 2 2
3 1 1 2
Output
3.414213562373095048801688724
4.828427124746190097603377448


The route of the $1$-st participant is shown by the red dotted line, and that of the $2$-nd participant by the blue line. Note that logs may cross each other.

Sample 3
Input
5 5
8808 -2051 -3691 1776
-9697 -4260 -4971 -5119
6418 873 -7379 1473
9760 -4164 -6052 -7422
-2542 107 7881 -6992
4 1 1 2
3 1 5 1
3 2 5 2
5 2 3 1
3 2 1 2
Output
16243.29816644555816987499627
15329.82119913967391662529792
21443.82128111283344796709709
9489.371445617676854468967106
3700.426056550785882761689606

Sample 4
Input
3 1
1 2 9 8
5 2 1 0
1 4 1 7
1 1 2 2
Output
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。