There are \(N\) points in a 2D plane. You wish to find a rectangle with sides parallel to the \(x\) and \(y\) axes which covers all the points. What is the smallest area of such a rectangle?
First, suppose that we want to minimise just the width of the rectangle. We only need to look at the \(x\) coordinates, as \(y\)-coordinates only impact the height of the rectangle.
The width must be at least the difference between the smallest and largest \(x\)-coordinates, as any rectangle which covers all the points must be at least this wide.
However, there is no need for the rectangle to be wider than this - if it was, we could just shrink the width while still ensuring it covers all the points.
Therefore, the smallest width is the difference between the maximum and minimum \(x\)-coordinates.
Similarly, the smallest height is the difference between the maximum and minimum \(y\)-coordinates.
The smallest area is the smallest width multiplied by the smallest height.
import sys
sys.setrecursionlimit(1000000000)
# N is the number of holes.
N = None
# x and y contain the locations of the holes.
x = [None for x in range(100005)]
y = [None for x in range(100005)]
answer = None
# Open the input and output files.
input_file = open("artin.txt", "r")
output_file = open("artout.txt", "w")
# Read the value of N.
N = int(input_file.readline().strip())
# Read the location of each hole.
for i in range(0, N):
input_line = input_file.readline().strip()
x[i], y[i] = map(int, input_line.split())
# Resize the arrays to only include the N points
x = x[:N]
y = y[:N]
# Find the area
width = max(x) - min(x)
height = max(y) - min(y)
answer = width*height
# Write the answer to the output file.
output_file.write("%d\n" % (answer))
# Finally, close the input/output files.
input_file.close()
output_file.close()