Kesulitan berbagi pizza dengan teman-teman adalah sulit untuk memastikan bahwa setiap orang mendapatkan jumlah pepperoni yang sama pada potongan mereka. Jadi, tugas Anda adalah memutuskan cara mengiris pizza agar semua orang senang.

Petunjuk arah

Tulis sebuah program yang, diberi daftar posisi pepperonis pada pizza bundar dan jumlah irisan yang akan dibuat, menampilkan daftar sudut tempat pizza harus dipotong sehingga setiap irisan memiliki jumlah pepperoni yang sama pada Itu.

• Pizza hanya memiliki satu topping: pepperoni.
• Teman Anda tidak peduli tentang ukuran irisan mereka, hanya saja mereka tidak tertipu oleh pepperoni apa pun.
• Pizza adalah lingkaran yang berpusat pada titik asal (0, 0)dan dengan jari-jari1 .
• Pepperonis adalah lingkaran yang berpusat di mana pun input mengatakan mereka berpusat dan memiliki jari-jari0.1
• Ambil input sebagai bilangan bulat yang mewakili jumlah irisan yang akan dibuat dan daftar pasangan berurutan yang mewakili posisi pepperonis pada sistem koordinat kartesius. (Dalam format apa pun yang masuk akal)
• Keluaran harus berupa daftar sudut yang diberikan dalam radian yang mewakili posisi "pemotongan" ke pizza (dalam kisaran0 <= a < 2pi ). (Dalam format apa pun yang masuk akal) (Presisi setidaknya harus +/- 1e-5.)
• Anda dapat memiliki sebagian potongan pepperoni di sepotong (mis. Jika pizza memiliki satu pepperoni di atasnya dan perlu dibagi oleh 10 orang, potong pizza sepuluh kali, semua potongan mengiris pepperoni. Tetapi pastikan itu adil !)
• Potongan dapat (mungkin harus) mengiris beberapa pepperonis.
• Pepperonis mungkin tumpang tindih.

Contohnya

Memasukkan:

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

Kemungkinan hasil yang valid:

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

Berikut adalah visualisasi dari contoh ini (setiap orang mendapat setengah pepperoni):

Lebih banyak contoh:

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

Mencetak gol

Ini adalah kode-golf , jadi paling tidak jumlah byte yang menang.

Mathematica, 221 byte

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

Tidak Disatukan:

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

Ini mendefinisikan fungsi yang mengambil parameter jumlah irisan dan daftar pasangan untuk koordinat peperoni, seperti

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

Ini akan mencetak irisan ke konsol saat melintasi pizza.

Pada kebanyakan pizza, ini cukup lambat, karena (untuk mencapai presisi yang diperlukan) saya mengintegrasikan area peperoni dari 0 ke 2π dalam langkah 1e-5. Untuk mendapatkan hasil yang sedikit kurang tepat dalam jumlah waktu yang masuk akal, Anda dapat mengubah 1.*^-5di akhir 1.*^-3.

Bagaimana itu bekerja

Idenya adalah untuk menyapu irisan pizza sambil menyatukan area potongan peperoni tertutup. Setiap kali area itu mencapai jumlah peperoni yang diperlukan per orang, kami melaporkan sudut saat ini dan mengatur ulang penghitung area.

Untuk mendapatkan area peperoni yang tersapu, kami memotong garis dengan peperoni untuk menggunakan dua jarak dari titik asal, di mana garis tersebut bersilangan dengan peperoni. Karena garis meluas hingga tak terbatas di kedua arah, kita perlu menjepit jarak ini ke nilai-nilai non-negatif. Ini memecahkan dua masalah:

• Menghitung persimpangan dengan masing-masing peperoni dua kali, sekali positif dan sekali negatif (yang benar-benar akan menghasilkan luas keseluruhan 0).
• Hanya menghitung irisan potongan peperoni yang termasuk dalam asal.

Saya akan menyertakan beberapa diagram nanti.