CCC '01 S4 - Cookies

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type
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 n not greater than 10, followed by n lines of input.

Each line gives the coordinates of one chocolate chip on the plane.

Each coordinate is an integer in the range [0, 1000].

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


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

    one test case wrong, no idea why


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

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


      • 1
        wleung_bvg  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)


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

          Not sure if I'm doing this wrong but for the case above w/ (0,0), (0,10), (5,6) isn't 10.00 still the correct answer? It's a circle centered at (0.1,5) with diameter 2\times\sqrt{25.01} and all 3 chocolate chips on its circumference.


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

          Yes I believe there is a little more trig involved.


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

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


            • 0
              rpeng  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.


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

                or use long double


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

              Alright