CCC '01 S4 - Cookies

View as PDF
Submit solution
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 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


  • 0
    AtharvG  commented on Oct. 31, 2024, 11:51 p.m.

    To anyone who is seriously having trouble with this:

    Research Welzl's algorithm


  • 3
    Pleedoh  commented on May 22, 2017, 3:47 p.m.

    one test case wrong, no idea why


    • 4
      MackenzieTeam3  commented on May 29, 2017, 1:18 a.m.

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


      • 3
        wleung_bvg  commented on May 29, 2017, 1:25 p.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)


        • 1
          Jinx  commented on July 3, 2020, 9:36 p.m.

          Welp I did it wrong then lol


        • 10
          abcConjecture  commented on Jan. 22, 2018, 11: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.


          • 1
            noYou  commented on March 4, 2020, 12:35 a.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.


        • -3
          Pleedoh  commented on May 29, 2017, 6:14 p.m.

          Yes I believe there is a little more trig involved.


          • 5
            wleung_bvg  commented on May 29, 2017, 6:38 p.m.

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


            • 4
              rpeng  commented on Aug. 4, 2019, 5: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.


              • -6
                discoverMe  commented on Aug. 4, 2019, 7:25 p.m.

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


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

              Alright