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):  The second sample is (*r*12 = 1, *r*22 = 32): 