codeforces-scrape

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

702C.md (1920B)


      1 Source: https://codeforces.com/problemset/problem/702/C
      2 
      3 C. Cellular Network
      4 
      5 time limit per test
      6 
      7 3 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 You are given *n* points on the straight line — the positions (*x*-coordinates) of the cities and *m* points on the same line — the positions (*x*-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than *r* from this tower.
     22 
     23 Your task is to find minimal *r* that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than *r*.
     24 
     25 If *r* = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than *r* from this tower.
     26 
     27 Input
     28 
     29 The first line contains two positive integers *n* and *m* (1 ≤ *n*, *m* ≤ 105) — the number of cities and the number of cellular towers.
     30 
     31 The second line contains a sequence of *n* integers *a*1, *a*2, ..., *a**n* ( - 109 ≤ *a**i* ≤ 109) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates *a**i* are given in non-decreasing order.
     32 
     33 The third line contains a sequence of *m* integers *b*1, *b*2, ..., *b**m* ( - 109 ≤ *b**j* ≤ 109) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates *b**j* are given in non-decreasing order.
     34 
     35 Output
     36 
     37 Print minimal *r* so that each city will be covered by cellular network.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 2  
     45 -2 2 4  
     46 -3 0
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 4
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 5 3  
     59 1 5 10 14 17  
     60 4 11 15
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 ```