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.
#!/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()