codeforces-scrape

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

617C.md (1962B)


      1 Source: https://codeforces.com/problemset/problem/617/C
      2 
      3 C. Watering Flowers
      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 A flowerbed has many flowers and two fountains.
     22 
     23 You can adjust the water pressure and set any values *r*1(*r*1 ≥ 0) and *r*2(*r*2 ≥ 0), giving the distances at which the water is spread from the first and second fountain respectively. You have to set such *r*1 and *r*2 that all the flowers are watered, that is, for each flower, the distance between the flower and the first fountain doesn't exceed *r*1, or the distance to the second fountain doesn't exceed *r*2. It's OK if some flowers are watered by both fountains.
     24 
     25 You need to decrease the amount of water you need, that is set such *r*1 and *r*2 that all the flowers are watered and the *r*12 + *r*22 is minimum possible. Find this minimum value.
     26 
     27 Input
     28 
     29 The first line of the input contains integers *n*, *x*1, *y*1, *x*2, *y*2 (1 ≤ *n* ≤ 2000,  - 107 ≤ *x*1, *y*1, *x*2, *y*2 ≤ 107) — the number of flowers, the coordinates of the first and the second fountain.
     30 
     31 Next follow *n* lines. The *i*-th of these lines contains integers *x**i* and *y**i* ( - 107 ≤ *x**i*, *y**i* ≤ 107) — the coordinates of the *i*-th flower.
     32 
     33 It is guaranteed that all *n* + 2 points in the input are distinct.
     34 
     35 Output
     36 
     37 Print the minimum possible value *r*12 + *r*22. Note, that in this problem optimal answer is always integer.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2 -1 0 5 3  
     45 0 2  
     46 5 2
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 6
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 4 0 0 5 0  
     59 9 4  
     60 8 3  
     61 -1 0  
     62 1 4
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 33
     69 ```
     70 
     71 Note
     72 
     73 The first sample is (*r*12 = 5, *r*22 = 1): ![](https://espresso.codeforces.com/b22bc3b9d5e08270abeb227926f71a59c047471e.png) The second sample is (*r*12 = 1, *r*22 = 32): ![](https://espresso.codeforces.com/52cff766dc5ed8406cad96178771df70a1edc042.png)