codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1886B.md (2437B)


      1 Source: https://codeforces.com/problemset/problem/1886/B
      2 
      3 B. Fear of the Dark
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Monocarp tries to get home from work. He is currently at the point $O = (0, 0)$ of a two-dimensional plane; his house is at the point $P = (P_x, P_y)$.
     22 
     23 Unfortunately, it is late in the evening, so it is very dark. Monocarp is afraid of the darkness. He would like to go home along a path illuminated by something.
     24 
     25 Thankfully, there are two lanterns, located in the points $A = (A_x, A_y)$ and $B = (B_x, B_y)$. You can choose any non-negative number $w$ and set the power of both lanterns to $w$. If a lantern's power is set to $w$, it illuminates a circle of radius $w$ centered at the lantern location (including the borders of the circle).
     26 
     27 You have to choose the minimum non-negative value $w$ for the power of the lanterns in such a way that there is a path from the point $O$ to the point $P$ which is completely illuminated. You may assume that the lanterns don't interfere with Monocarp's movement.
     28 
     29  ![](https://espresso.codeforces.com/81b6c69f2f20ed3e39faa6a111fcbcc784ae344b.png) The picture for the first two test cases
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 Each test case consists of three lines:
     36 
     37 * the first line contains two integers $P_x$ and $P_y$ ($-10^3 \le P_x, P_y \le 10^3$) — the location of Monocarp's house;
     38 * the second line contains two integers $A_x$ and $A_y$ ($-10^3 \le A_x, A_y \le 10^3$) — the location of the first lantern;
     39 * the third line contains two integers $B_x$ and $B_y$ ($-10^3 \le B_x, B_y \le 10^3$) — the location of the second lantern.
     40 
     41 Additional constraint on the input:
     42 
     43 * in each test case, the points $O$, $P$, $A$ and $B$ are different from each other.
     44 
     45 Output
     46 
     47 For each test case, print the answer on a separate line — one real number equal to the minimum value of $w$ such that there is a completely illuminated path from the point $O$ to the point $P$.
     48 
     49 Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$ — formally, if your answer is $a$, and the jury's answer is $b$, your answer will be accepted if $\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 2
     57 
     58 3 3
     59 
     60 1 0
     61 
     62 -1 6
     63 
     64 3 3
     65 
     66 -1 -1
     67 
     68 4 3
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 3.6055512755
     75 3.2015621187
     76 ```