P2 - LOL

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Josh is playing his favorite game, Legal Legends. In the game, Josh has to command and select units, by drawing a rectangle that contains them. On Josh's screen, there are N units, with the i^{th} unit having the coordinates (X_i, Y_i), Josh is lazy, and does not want to draw larger rectangles than he needs to. Help Josh figure out the minimum area of the rectangle required to contain all the units on his screen. A unit is considered contained in a rectangle if it is either inside the rectangle, or on one of its edges.

Input Specification

The first line will contain the integer N (2 \leq N \leq 100\,000), the number of units on Josh's screen. The next N lines contains 2 integers each, the i^{th} line containing (X_i, Y_i), (-1000 \leq X_i, Y_i \leq 1000), the coordinates of the i^{th} unit.

Output Specification

Output the minimum area required to contain Josh's units.

Sample Input 1

0 2
0 0
2 0
2 2

Sample Output 1


Sample Input 2

1 2
1 3
1 4

Sample Output 2



  • 0
    Jonathan_Uy  commented on May 17, 2020, 4:52 a.m.

    This question is almost exactly the same as VM7WC '16 #3 Bronze - Shahir-in-a-Box, which is worth three points.

    • 0
      boolean  commented on May 23, 2020, 10:26 a.m.

      However, the rectangles in that problem must be axis-aligned, whereas in this problem there is no such constraint.