SRM 607, D2, 250-Pointer (BoundingBox)

James S. Plank

Mon Sep 30 11:51:42 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
A shell script for testing.
The correct output for tests.sh.
Problem Given in Topcoder: 2014
Competitors who opened the problem: 1102
Competitors who submitted a solution: 1011
Number of correct solutions: 974
Accuracy (percentage correct vs those who opened): 88.4%
Average Correct Time: 12 minutes, 14 seconds.

In case Topcoder's servers are down

Please use the workflow in the problem Cryptography. You can test yourself with tests.sh, and your output should match answers.txt. The problems in tests.sh go up to 1000 points in size -- your program should solve these in the blink of an eye.

Here is a summary of the problem:

You are given two vectors of integers, X and Y.
The two vectors are the same size and contain integers between -1000 and 1000.
The vectors define cartesian coordinates. The points are (X[i],Y[i]) for 0 ≤ i < X.size().
Suppose you draw a rectangle whose sides are parallel to the x and y axes, and suppose that the rectangle contains all of the points.
Return the smallest possible area of a rectangle that does this.
The problem will guarantee that the area will be greater than zero.

Examples

Example	X	Y	Answer
0	`{0,1}`	`{1,0}`	`1`
1	`{0,-2,-1}`	`{-1,-1,-2}`	`2`
2	`{0,0,1,0,-1,2}`	`{0,1,2,-2,0,-1}`	`12`
3	`{9,-88,-40,98,-55,41,-38}`	`{-65,56,-67,7,-58,33,68}`	`25110`

Try this one on your own first. I suggest graphing examples 1 and 2, and the answer should fall out pretty naturally.

The bounding box will be defined by the:

Minimum x value, minx
Maximum x value, maxx
Minimum y value, miny
Maximum y value, maxy

The width of the bounding box is maxx-minx, and the height is maxy-miny.