Problem 2 - Art Class II

Summary

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?

Solution

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.

Code

#!/usr/bin/env python
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)]

# Open the input and output files.
input_file = open("artin.txt", "r")
output_file = open("artout.txt", "w")

# Read the value of N.

# Read the location of each hole.
for i in range(0, N):
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)