codeforces-scrape

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

485B.md (1522B)


      1 Source: https://codeforces.com/problemset/problem/485/B
      2 
      3 B. Valuable Resources
      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 Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems.
     22 
     23 Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates. The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square.
     24 
     25 Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.
     26 
     27 Input
     28 
     29 The first line of the input contains number *n* — the number of mines on the map (2 ≤ *n* ≤ 1000). Each of the next *n* lines contains a pair of integers *x**i* and *y**i* — the coordinates of the corresponding mine ( - 109 ≤ *x**i*, *y**i* ≤ 109). All points are pairwise distinct.
     30 
     31 Output
     32 
     33 Print the minimum area of the city that can cover all the mines with valuable resources.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 2  
     41 0 0  
     42 2 2
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 4
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 2  
     55 0 0  
     56 0 3
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 9
     63 ```