Appleby Contest '19 P4 - Rectangles - DMOJ: Modern Online Judge

Appleby Contest '19 P4 - Rectangles

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 0.5s

Memory limit: 64M

Python 256M

Author:

Plasmatic

Problem types

King Brian is looking at rectangles!

He has a list of $N$ $N$ points $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})$ and can select any four at random. If the four points form the four corners of an axis aligned rectangle, he writes down the area.

What is the largest possible area he can get from selecting four random points?

Note: axis aligned means that the four lines that form the rectangle are all either horizontal or vertical (aligning with the $x$ $x$ and $y$ $y$ axes respectively).

Constraints

For all subtasks:

$4 \le N \le 2 \times 10^3$ $4 \leq N \leq 2 \times 10^{3}$

$1 \le |x_i|, |y_i| \le 2 \times 10^4$ $1 \leq | x_{i} |, | y_{i} | \leq 2 \times 10^{4}$

No two points will be the same.

Subtask 1 [15%]

$1 \le N \le 50$ $1 \leq N \leq 50$

Subtask 2 [70%]

$1 \le N \le 500$ $1 \leq N \leq 500$

Subtask 3 [15%]

No additional constraints.

Input Specification

The first line will contain the integer $N$ $N$ .

The next $N$ $N$ lines will each contain two space separated integers: $x_i$ $x_{i}$ , $y_i$ $y_{i}$ .

Output Specification

Output one line, the maximum possible area of an axis aligned rectangle King Brian can get from selecting four random points. If no rectangles can be formed, print $0$ $0$ .

Sample Input

Copy

Sample Output

Copy

Sample Explanation

There are two possible rectangles that can be constructed with the $9$ $9$ points:

From $(5, 5)$ $(5, 5)$ to $(7, 7)$ $(7, 7)$ with an area of $4$ $4$
From $(5, 5)$ $(5, 5)$ to $(10, 10)$ $(10, 10)$ with an area of $25$ $25$

Thus the answer is $25$ $25$ .

Comments

0

Humanthe2nd commented on Nov. 17, 2024, 2:31 a.m.

Negative coordinates are possible. I'm dumb and missed that in the constraints.

0

thunder200911133 commented on Feb. 12, 2024, 7:08 p.m.

from (1,1) to (20,20) with an area of 361 what?

0

thunder200911133 commented on March 20, 2024, 2:58 p.m.

guys, nvm, I get it, we have to have all 4 points in the points list, python3 is a bit hard

0

Sam629566 commented on Sept. 12, 2024, 1:43 a.m. ← edited →

your code works in pypy3 (erm oops didn't know u solved it)