## Mock CCO '18 Contest 2 Problem 4 - Victor's Rectangles

View as PDF

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 64M

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

Roger, having figured out how to reason in two dimensions, has crafted a tricky puzzle for Victor to crack.

Roger has highlighted several lattice points in the -plane and wants Victor to find the rectangle with maximum area inside that has vertices among the highlighted points!

Victor takes a look at this task and scoffs. It's just a line sweep problem, what's so tricky about that?

However, Roger points out to Victor that the rectangle need not be axis-aligned. The rectangles, much like Roger, can be tilted.

Is Victor tilt-proof?

#### Constraints

For at most 20% of full credit, .

All are distinct.

#### Input Specification

The first line will contain a single integer, .

Each of the next lines will contain two space-separated integers and , indicating that Roger has highlighted point .

#### Output Specification

Print, on a single line, the maximum area of a rectangle with lattice points among the highlighted points. It is guaranteed that a non-degenerate rectangle exists.

#### Sample Input

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

#### Sample Output

10