A dificuldade em compartilhar pizza com os amigos é que é difícil garantir que todos recebam a mesma quantidade de pepperoni na fatia. Portanto, sua tarefa é decidir como fatiar uma pizza de maneira justa para que todos fiquem felizes.

instruções

Escreva um programa que, dada uma lista das posições dos pepperonis em uma pizza circular e o número de fatias a serem produzidas, produza uma lista dos ângulos em que a pizza deve ser cortada para que cada fatia tenha a mesma quantidade de pepperoni isto.

• A pizza tem apenas uma cobertura: calabresa.
• Seus amigos não se importam com o tamanho de sua fatia, apenas porque eles não são enganados por nenhum pepperoni.
• A pizza é um círculo centrado na origem (0, 0)e com um raio de1 .
• Os pepperonis são círculos centralizados onde quer que a entrada diga que estão centralizados e têm um raio de0.1
• Tome a entrada como um número inteiro que representa o número de fatias a serem feitas e uma lista de pares ordenados que representam as posições dos pepperonis em um sistema de coordenadas cartesianas. (Em qualquer formato razoável)
• A saída deve ser uma lista de ângulos dados em radianos que representam as posições dos "cortes" na pizza (no intervalo0 <= a < 2pi ). (Em qualquer formato razoável) (a precisão deve ser no mínimo +/- 1e-5.)
• Você pode colocar pedaços parciais de calabresa em uma fatia (por exemplo, se uma pizza tem uma calabresa e ela precisa ser compartilhada por 10 pessoas, corte a pizza dez vezes, todos os cortes cortando a calabresa. !)
• Um corte pode (pode ser necessário) cortar vários pepperonis.
• Pepperonis pode se sobrepor.

Exemplos

Entrada:

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

Possível saída válida:

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

Aqui está uma visualização deste exemplo (todos recebem meia calabresa):

Mais exemplos:

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

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

Pontuação

Isso é código-golfe , portanto, o menor número de bytes vence.

Mathematica, 221 bytes

f=(A=Pi.01Length@#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]])&

Ungolfed:

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]
   ]
) &

Isso define uma função que assume como parâmetros o número de fatias e uma lista de pares para as coordenadas do peperoni, como

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

Ele imprimirá as fatias no console enquanto atravessa a pizza.

Na maioria das pizzas, isso é bastante lento, porque (para obter a precisão necessária) estou integrando a área de peperoni de 0 a 2π nas etapas de 1e-5. Para obter um resultado um pouco menos preciso em um período de tempo razoável, você pode alterar o 1.*^-5no final para 1.*^-3.

Como funciona

A idéia é varrer as fatias de pizza enquanto se integra na área dos pedaços de peperoni cobertos. Sempre que a área atingir a quantidade necessária de peperoni por pessoa, reportamos o ângulo atual e redefinimos o contador de áreas.

Para obter a área de peperoni varrida, cruzamos a linha com o peperoni para usar as duas distâncias da origem, onde a linha se cruza com o peperoni. Como uma linha se estende até o infinito em ambas as direções, precisamos fixar essas distâncias em valores não negativos. Isso resolve dois problemas:

• Contar interseções com cada peperoni duas vezes, uma vez positivas e uma vez negativas (o que resultaria em uma área total de 0).
• Contando apenas fatias de pedaços de peperoni que incluem na origem.

Vou incluir alguns diagramas mais tarde.