## CCC '01 S4 - Cookies

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem types
##### 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

• commented on May 22, 2017, 11:47 a.m.

one test case wrong, no idea why

• commented on May 28, 2017, 9:18 p.m.

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

• commented on May 29, 2017, 9:25 a.m.

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)

• commented on July 3, 2020, 5:36 p.m.

Welp I did it wrong then lol

• commented on Jan. 22, 2018, 6:53 p.m.

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.

• commented on March 3, 2020, 7:35 p.m. edited

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

• commented on May 29, 2017, 2:14 p.m.

Yes I believe there is a little more trig involved.

• commented on May 29, 2017, 2:38 p.m.

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

• commented on Aug. 4, 2019, 1:25 p.m.

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.

• commented on Aug. 4, 2019, 3:25 p.m.

or use long double

• commented on May 29, 2017, 3:50 p.m.

Alright