Trudność w dzieleniu się pizzą z przyjaciółmi polega na tym, że trudno jest upewnić się, że wszyscy dostają taką samą ilość pepperoni na swoim kawałku. Twoim zadaniem jest zdecydować, jak sprawiedliwie pokroić pizzę, aby wszyscy byli zadowoleni.

Kierunki

Napisz program, który, biorąc pod uwagę listę pozycji pepperoni na okrągłej pizzy i liczbę plasterków do zrobienia, wyświetla listę kątów, pod którymi pizza powinna być pokrojona, aby każdy plasterek miał taką samą ilość pepperoni na to.

• Pizza ma tylko jeden dodatek: pepperoni.
• Twoi przyjaciele nie dbają o rozmiar swojego plasterka, tylko że nie są oszukani z żadnego pepperoni.
• Pizza jest kołem wyśrodkowanym na początku (0, 0)i promieniu1 .
• Peponiony są okręgami, które są wyśrodkowane wszędzie tam, gdzie dane wejściowe mówią, że są wyśrodkowane i mają promień0.1
• Weź dane wejściowe jako liczbę całkowitą reprezentującą liczbę wycinków do wykonania i listę uporządkowanych par reprezentujących pozycje pepperonis w kartezjańskim układzie współrzędnych. (W dowolnym rozsądnym formacie)
• Wyjściem powinna być lista kątów podana w radianach, która reprezentuje pozycje „cięć” pizzy (w zakresie0 <= a < 2pi ). (W dowolnym rozsądnym formacie) (Precyzja powinna być co najmniej +/- 1e-5.)
• Na plasterku możesz mieć częściowe kawałki pepperoni (np. Jeśli pizza ma jeden pepperoni i musi być dzielony przez 10 osób, pokrój pizzę dziesięć razy, wszystkie kawałki pokrój przez pepperoni. Ale upewnij się, że jest sprawiedliwa !)
• Kawałek może (może trzeba) przeciąć wiele pepperoni.
• Pepperoni mogą się nakładać.

Przykłady

Wejście:

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

Możliwe prawidłowe dane wyjściowe:

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

Oto wizualizacja tego przykładu (każdy dostaje pół pepperoni):

Więcej przykładów:

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

Punktacja

To jest golf golfowy , więc wygrywa najmniejsza liczba bajtów.

Mathematica, 221 bajtów

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

Nie golfowany:

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

Definiuje funkcję, która przyjmuje jako parametry liczbę plasterków i listę par dla współrzędnych peperoni, takich jak

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

Wydrukuje plasterki na konsoli, gdy przemierza pizzę.

W przypadku większości pizz jest to dość wolne, ponieważ (aby osiągnąć wymaganą precyzję) integruję obszar peperoni od 0 do 2π w krokach 1e-5. Aby uzyskać nieco mniej dokładny wynik w rozsądnym czasie, możesz zmienić 1.*^-5na końcu na 1.*^-3.

Jak to działa

Chodzi o to, aby zmieść plasterki pizzy, jednocześnie integrując obszar pokrytych kawałków peperoni. Ilekroć ten obszar osiągnie wymaganą ilość peperoni na osobę, raportujemy aktualny kąt i resetujemy licznik powierzchni.

Aby uzyskać zmieszany obszar peperoni, przecinamy linię z peperoni, aby wykorzystać dwie odległości od początku, gdzie linia przecina się z peperoni. Ponieważ linia rozciąga się do nieskończoności w obu kierunkach, musimy ograniczyć te odległości do wartości nieujemnych. To rozwiązuje dwa problemy:

• Zliczanie przecięć z każdym peperoni dwa razy, raz dodatni i raz ujemny (co w rzeczywistości dałoby całkowity obszar 0).
• Licząc tylko kliny kawałków peperoni, które są zawarte w pochodzeniu.

Później dołączę kilka diagramów.