507B.md (1406B)
1 Source: https://codeforces.com/problemset/problem/507/B 2 3 B. Amr and Pins 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Amr loves Geometry. One day he came up with a very interesting problem. 22 23 Amr has a circle of radius *r* and center in point (*x*, *y*). He wants the circle center to be in new position (*x*', *y*'). 24 25 In one step Amr can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin. 26 27 Help Amr to achieve his goal in minimum number of steps. 28 29 Input 30 31 Input consists of 5 space-separated integers *r*, *x*, *y*, *x*' *y*' (1 ≤ *r* ≤ 105, - 105 ≤ *x*, *y*, *x*', *y*' ≤ 105), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively. 32 33 Output 34 35 Output a single integer — minimum number of steps required to move the center of the circle to the destination point. 36 37 Examples 38 39 Input 40 41 ``` 42 2 0 0 0 4 43 ``` 44 45 Output 46 47 ``` 48 1 49 ``` 50 51 Input 52 53 ``` 54 1 1 1 4 4 55 ``` 56 57 Output 58 59 ``` 60 3 61 ``` 62 63 Input 64 65 ``` 66 4 5 6 5 6 67 ``` 68 69 Output 70 71 ``` 72 0 73 ``` 74 75 Note 76 77 In the first sample test the optimal way is to put a pin at point (0, 2) and rotate the circle by 180 degrees counter-clockwise (or clockwise, no matter). 78 79 