##### Canadian Computing Competition: 2001 Stage 1, Senior #4

Making chocolate chip cookies involves mixing flour, salt, oil, baking soda and chocolate chips to form dough which is rolled into a plane. Circles are cut from the plane, placed on a cookie sheet, and baked in an oven for about twenty minutes. When the cookies are done, they are removed from the oven and allowed to cool before being eaten.

We are concerned here with the process of cutting a single round cookie that contains all the chocolate chips. Once the dough has been rolled, each chip is visible in the planar dough, so we need simply to find a cookie cutter big enough to circle all the chips. What is the diameter of the smallest possible round cookie containing all the chips?

#### Input Specification

Input consists of a positive integer not greater than , followed by lines of input. Each line gives the coordinates of one chocolate chip on the plane. Each coordinate is an integer in the range .

#### Output Specification

Output consists of a single real number, the diameter of the cookie rounded to two decimal places.

#### Sample Input 1

```
4
1 1
1 0
0 1
0 0
```

#### Sample Output 1

`1.41`

#### Sample Input 2

```
3
1 1
10 0
0 0
```

#### Sample Output 2

`10.00`

## Comments

To anyone who is seriously having trouble with this:

Research Welzl's algorithm

one test case wrong, no idea why

Yup, test case #4 is always wrong for some reason.

The answer is not simply the distance between the 2 furthest points.

Eg. Points (0, 0), (0, 10), and (5, 6) The answer is 10.17, not 10.00 (which is the distance between the 2 furthest points)

Welp I did it wrong then lol

Not sure if I'm doing this wrong but for the case above w/ isn't 10.00 still the correct answer? It's a circle centered at with diameter and all 3 chocolate chips on its circumference.

yep, if you use circumcentre this is the correct answer. Note that if you handle these special cases with circumcentre, it still passes.

Yes I believe there is a little more trig involved.

No trig is necessary. I would research Heron's formula.

Heron's is numerically unstable... need to subtract a few 4th powers. Calling Line-Line intersection on the perpendicular bisectors is the way to go.

This comment is hidden due to too much negative feedback. Show it anyway.

Alright