ACSU Programming Competition

26 September 1998

Problem 2 - The Urabomber

Description

The most notorious criminal on Uranus is the Urabomber. The Uranoid police have records of the coordinates of all of his bombings. Due to the public transit system on Uranus, the Urabomber must live very close to the bombing sites. The police are going to completely surround the bombing sites, certain that the Urabomber must live within the surrounded area. Your job is to determine the perimeter of the surrounded area. Of course, the police have a limited budget, and will make the perimeter as small as possible, while still surrounding all the bombing sites.

Example

Suppose there are four bombing sites, at the coordinates (0,0), (3,0), (0,3), and (1,1). These are shown below on the left. On the right, we see the area that the police have surrounded. It has perimeter 10.243.

Input / Output

The first line of input will indicate the number of data sets. This number will be non-negative.

The first line of each data set contains one integer; call it n, which is 3 or greater. This is the number of bombing sites. The next n lines contain the 2-dimensional coordinates of the bombing sites, one per line.

For each data set, print the perimeter of the shape which contains all the bombing sites. The shape should have the smallest perimeter possible, while still containing all the bombing sites. Print the perimeter with 3 places after the decimal. Follow the format shown in Sample Output, below.

Sample

Sample Input

The comments to the right are not part of the actual input data.

2       There are two data sets.
4       The first data set has 4 bombing sites.
0 0     The first bombing site is at (0,0).
3 0
0 3
1 1
7       The second data set has 7 bombing sites.
0 0     The first bombing site is at (0,0).
1 0
2 0
-1 2
0 2
2 2
1 3

Sample Output

Data set 1: 10.243
Data set 2: 9.886

Solution

Here is the solution by David Kempe in C++.

Here is the test input:

Here is the correct output:

Data set 1: 10.243
Data set 2: 9.886
Data set 3: 4.829
Data set 4: 17.889

Last updated 28 September 1998.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.