VM7WC '16 #3 Bronze - Shahir-in-a-Box

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type

Shahir has a brilliant idea for his promposal: a delivered date! First, Shahir will enclose himself in a cardboard box, which will be taped shut and marked with postage. Then, he'll get some of his friends to dress up as mailmen, load the box into the back of a car, and drive to his date's house, at which he'll get his friends to carry the box to the front porch and ring the doorbell "to deliver a package". Once his prom date comes to the door and opens the box, she'll find Shahir inside, with a dress shirt, a tie, and a bouquet! That's the point where Shahir will ask her to prom.

It's the perfect plan. Nothing can go wrong. But first, Shahir needs to find the right box to sit in, since the car ride to his date's house is long and the box must be comfortable.

Shahir has figured out his convex hull: a set of 2D points that outline his body. He'd like to know the area of the smallest box, one with sides parallel to both axes, that fit all of his points. A point can lie on the boundary of a box.

Input Specification

On the first line will be a single positive integer N (3 \le N \le 10^5), the number of points that outline Shahir. The next N lines will each contain two integers x and y (0 \le x, y \le 1000), where (x, y) gives the coordinate pair for a point on Shahir's outline. The N points will never be collinear, Shahir's convex hull will never have an area of zero, and the same point will not be given twice.

Note: Fast IO is recommended.

Output Specification

On a single line, print the area of the smallest box that can contain all N points.

Sample Input

0 0
4 0
0 3

Sample Output



There are no comments at the moment.