Richmond Green P2 - LOL

View as PDF

Submit solution

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

Problem type

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 contains the integer N (2 \le N \le 100\,000), the number of units on Josh's screen. The next N lines contain 2 integers each, the i^{th} line containing (X_i, Y_i), (-1000 \le X_i, Y_i \le 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



  • -1
    Ch4rIes  commented on April 5, 2021, 12:01 a.m.

    CCC stole this problem

  • -1
    Jonathan_Uy  commented on May 17, 2020, 8:52 a.m.

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

    • 2
      boolean  commented on May 23, 2020, 2:26 p.m.

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