Description

Sometimes Bear's owners [1] like to go outside and have a nice picnic. This not only provides them with an opportunity to relax and enjoy the beautiful northern Indiana landscape [2], but also allows Bear to be outside and roam around and do the things huskies do.

Of course, Bear just gets so excited when she is outside and loves to run around in a crazed and almost feral manner. To prevent her from running off, her owners tie her leash to a tree and let her do as she pleases. Every once in a while, out of nowhere, she goes in that crazy feral mood and just starts running in circles.

On occasion she will run all around the whole picnic party, attempting to encircle everyone with her leash. For this problem, you are to figure out how much leash she needs to completely wrap everyone in the picnic area. Note that she already uses 1 foot of leash for the initial knot around the tree and requires an additional foot after she encircles everyone for a complete encapsulation.

Input

In this problem, Bear is tied to a tree located at (0, 0). People are picnicing around her at various locations. The input will consist of a series of possible arrangements of people. The first line in a set will indicate the number of people in the set, followed by their locations X Y, one location per line. Here is an sample input:

4
1.0 1.0
-1.0 1.0
-1.0 -1.0
1.0 -1.0

Output

Assuming the the leash is taught and held tight by Bear and accounting for the amount of leash used to tie her to the tree, what is the minimum amount of leash required to encircle the whole picnic party. Output this amount to two decimal places. Here is an sample output:

10.83

[1]	To Bear, her servants.

[2]	Out under the day star, upon the gentle flatlands, winter's longing cold whisper swirls about you...

Approach

Read in the locations as points and then compute the convex hull. Deal with the various cases where the pole may or may not be in the convex hull. If not, then, determine the optimal location to insert the pole in the computed hull.

Input/Output

• Final input: problem024.input
• Final output: problem024.output

Source Code

• Peter Bui's source code: pbui.cc
• Noah Franske's source code: nfranske.cc