CCCHK '15 J2 - What is the minimum area?

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

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

There are N points in a 2D plane. You can place any square on the plane as long as the square is rectilineary oriented, i.e., its sides are paralleled to the x and y axis. What is the minimum area of a square that can cover at least two points in the plane?

Input Specification

  • The first line contains one integer N (2 \le N \le 100) representing the number of points in the plane.
  • The next N lines are the x and y coordinates of the points. The x and y coordinate values are separated by a space. It is guaranteed that x and y are integers and in the range of [-10\,000, 10\,000].
  • You can assume that the points are unique.

Output Specification

An integer represents the minimum area of a square that can cover at least two points in the plane.

Sample Input 1

3
0 0
2 1
-2 -4

Output for Sample Input 1

4

Explanation for Sample Input 1

A possible square is with the lower left corner and upper right corner locating at (0,0) and (2,2), which can cover points (0,0) and (2,1). The area of this square is 4.

Sample Input 2

3
0 0
2 2
3 3

Output for Sample Input 2

1

Explanation for Sample Input 2

A possible square is with the lower left corner and upper right corner locating at (2,2) and (3,3), which can cover points (2,2) and (3,3). The area of this square is 1.


Comments

There are no comments at the moment.