The difficulty with sharing pizza with friends is that it is hard to make sure that everyone gets the same amount of pepperoni on their slice. So, your task is to decide how to fairly slice a pizza so that everyone is happy.


Write a program that, given a list of the positions of pepperonis on a circular pizza and the number of slices to be made, outputs a list of the angles that the pizza should be cut at so that each slice has the same amount of pepperoni on it.

  • The pizza has only one topping: pepperoni.
  • Your friends don't care about the size of their slice, just that they are not cheated out of any pepperoni.
  • The pizza is a circle centered on the origin (0, 0) and with a radius of 1.
  • The pepperonis are circles that are centered wherever the input says they are centered and have a radius of 0.1
  • Take input as an integer that represents the number of slices to be made and a list of ordered-pairs that represent the positions of the pepperonis on a cartesian coordinate system. (In any reasonable format)
  • Output should be a list of angles given in radians that represents the positions of the "cuts" to the pizza (in the range 0 <= a < 2pi). (In any reasonable format) (Precision should be to at least +/- 1e-5.)
  • You can have partial pieces of a pepperoni on a slice (eg. If a pizza has one pepperoni on it and it needs to be shared by 10 people, cut the pizza ten times, all cuts slicing through the pepperoni. But make sure it's fair!)
  • A cut can (may have to) slice through multiple pepperonis.
  • Pepperonis may overlap.



8 people, pepperonis: (0.4, 0.2), (-0.3, 0.1), (-0.022, -0.5), (0.3, -0.32)

Possible valid output:

slices at:
0, 0.46365, 0.68916, 2.81984, 3.14159, 4.66842, 4.86957, 5.46554

Here is a visualisation of this example (everyone gets half a pepperoni):

enter image description here

More examples:

Input: 9 people, 1 pepperoni at: (0.03, 0.01)
Output: 0, 0.4065, 0.8222, 1.29988, 1.94749, 3.03869, 4.42503, 5.28428, 5.83985

enter image description here

Input: 5, (0.4, 0.3), (0.45, 0.43), (-0.5, -0.04)
Output: 0, 0.64751, 0.73928, 0.84206, 3.18997

enter image description here


This is , so least number of bytes wins.

  • \$\begingroup\$ To what precision must submissions adhere to be considered valid? \$\endgroup\$
    – Rainbolt
    Dec 19, 2014 at 1:27
  • \$\begingroup\$ @Rainbolt I would say that 4 or 5 decimal places should be enough. What do you suggest? I should add it to the question. \$\endgroup\$
    – kukac67
    Dec 19, 2014 at 1:28
  • \$\begingroup\$ I'm not sure that every problem is solvable. What if there are 7 slices and 3 pepperoni evenly spaced out? \$\endgroup\$ Dec 19, 2014 at 1:28
  • 1
    \$\begingroup\$ @NathanMerrill Then everyone would get 3/7 of a pepperoni. :) (Size of the slices doesn't matter.) \$\endgroup\$
    – kukac67
    Dec 19, 2014 at 1:30
  • 1
    \$\begingroup\$ Pizza hat attempt failed. Ask an easier one next time. ;) \$\endgroup\$ Dec 19, 2014 at 11:05

1 Answer 1


Mathematica, 221 bytes



f = (
   A = Pi .01 Length@#2/#;
   l = m /. Solve[Norm[{a, b} - m {Cos@t, Sin@t}] == .1, m];
   k = (l /. {a -> #, b -> #2}) & @@@ #2;
   d = 1.*^-5;
   For[Print[h = B = 0]; n = 1, n < #, h += d,
      B += If[Im@# < 0, 0, d (Max[#2, 0]^2 - Max[#, 0]^2)/2]
    ) & @@@ (k /. {t -> h});
    If[B > A, n += 1; Print@h; B -= A]
) &

This defines a function which takes as parameters the number of slices and a list of pairs for the peperoni coordinates, like

f[8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]

It will print the slices to the console as it traverses the pizza.

On most pizzas, this is fairly slow, because (to achieve the required precision) I'm integrating the peperoni area from 0 to 2π in steps of 1e-5. To get a slightly less precise result in a reasonable amount of time, you can change the 1.*^-5 at the end to 1.*^-3.

How it works

The idea is to sweep out the slices of pizza while integrating over the area of the peperoni pieces covered. Whenever that area hits the required amount of peperoni per person, we report the current angle and reset the area counter.

To obtain the peperoni area swept out, we intersect the line with the peperoni to give use the two distances from the origin, where the line intersects with the peperoni. Since a line extends to infinity in both directions, we need to clamp these distances to non-negative values. This solves two problems:

  • Counting intersections with each peperoni twice, once positive and once negative (which would actually yield to an overall area of 0).
  • Counting only wedges of peperoni pieces which include in the origin.

I'll include some diagrams later.

  • \$\begingroup\$ Yep. This was my plan of attack. At least I can more easily make examples now! :D \$\endgroup\$
    – kukac67
    Dec 19, 2014 at 12:11
  • \$\begingroup\$ I noticed that your implementation sometimes outputs one extra angle that would create an extra slice with no pepperoni on it. (for example with input: [8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]) \$\endgroup\$
    – kukac67
    Dec 21, 2014 at 22:31
  • \$\begingroup\$ @kukac67 fixed. \$\endgroup\$ Dec 23, 2014 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.