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)]

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()