codeforces-scrape

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

1012A.md (2244B)


      1 Source: https://codeforces.com/problemset/problem/1012/A
      2 
      3 A. Photo of The Sky
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Pavel made a photo of his favourite stars in the sky. His camera takes a photo of all points of the sky that belong to some rectangle with sides parallel to the coordinate axes.
     22 
     23 Strictly speaking, it makes a photo of all points with coordinates $(x, y)$, such that $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$, where $(x_1, y_1)$ and $(x_2, y_2)$ are coordinates of the left bottom and the right top corners of the rectangle being photographed. The area of this rectangle can be zero.
     24 
     25 After taking the photo, Pavel wrote down coordinates of $n$ of his favourite stars which appeared in the photo. These points are not necessarily distinct, there can be multiple stars in the same point of the sky.
     26 
     27 Pavel has lost his camera recently and wants to buy a similar one. Specifically, he wants to know the dimensions of the photo he took earlier. Unfortunately, the photo is also lost. His notes are also of not much help; numbers are written in random order all over his notepad, so it's impossible to tell which numbers specify coordinates of which points.
     28 
     29 Pavel asked you to help him to determine what are the possible dimensions of the photo according to his notes. As there are multiple possible answers, find the dimensions with the minimal possible area of the rectangle.
     30 
     31 Input
     32 
     33 The first line of the input contains an only integer $n$ ($1 \leq n \leq 100\,000$), the number of points in Pavel's records.
     34 
     35 The second line contains $2 \cdot n$ integers $a_1$, $a_2$, ..., $a_{2 \cdot n}$ ($1 \leq a_i \leq 10^9$), coordinates, written by Pavel in some order.
     36 
     37 Output
     38 
     39 Print the only integer, the minimal area of the rectangle which could have contained all points from Pavel's records.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4  
     47 4 1 3 2 3 2 1 3
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 1
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3  
     60 5 8 5 5 7 5
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 ```
     68 
     69 Note
     70 
     71 In the first sample stars in Pavel's records can be $(1, 3)$, $(1, 3)$, $(2, 3)$, $(2, 4)$. In this case, the minimal area of the rectangle, which contains all these points is $1$ (rectangle with corners at $(1, 3)$ and $(2, 4)$).