Cabaran TopCoder Open 2019: potong pai kepada enam bahagian

Di laluan “Kami menang: TopCoder Open 2019” Saya menerbitkan masalah daripada runut Algoritma (pengaturcaraan sukan klasik. Dalam satu setengah jam anda perlu menyelesaikan tiga masalah dalam Java, C#, C++ atau Python.)

1. Pai untuk enam

Pernyataan masalah

Had masa ialah 4 saat.

Anda mempunyai pai. Apabila dilihat dari atas, kek itu mempunyai bentuk poligon cembung (ketat). Anda diberi koordinat bucu dalam integer X dan Y.

Anda mempunyai lima kawan. Anda ingin membahagikan pai kepada enam keping kawasan yang sama (tetapi tidak semestinya bentuk yang sama). Sudah tentu, sesiapa sahaja boleh melakukannya dalam lima potong, tetapi hanya seorang profesional yang boleh melakukannya dalam tiga potong.

Cari tiga potongan garis lurus melalui satu titik yang akan membahagikan pai kepada enam bahagian yang sama. Cetak {x, y, d1, d2, d3}, dengan (x, y) ialah titik sepunya bagi ketiga-tiga potongan, dan d1, d2, d3 ialah sudut arah potongan dalam radian.

definisiKelas: CakeForSix
Kaedah: potong
Parameter: int[], int[] Pulangan: double[] Tandatangan kaedah: double[] cut(int[] x, int[] y)
(pastikan kaedah anda terbuka)

Nota

• Arah positif sepanjang paksi-x ialah 0 (radian), arah positif sepanjang paksi-y ialah pi/2 (radian).
• Potongan dalam arah d adalah serupa dengan potongan dalam arah pi*k+d untuk sebarang integer k.
• Anda boleh mengeluarkan sebarang arah, ia tidak perlu dari [0, pi).
• Penggred akan mengira luas enam keping kek anda dalam dua kali ganda. Jawapan akan diterima jika perbezaan relatif atau mutlak antara mereka adalah kurang daripada 10^(-4).
• Lebih tepat lagi, biarkan X dan Y menjadi yang terkecil dan terbesar daripada enam kawasan anda yang dikira oleh penggred. Maka jawapan anda akan diterima jika Y
• (Versi asal masalah menggunakan ketepatan 1e-7 dan bukannya 1e-4. Untuk menyelesaikan masalah ini dalam arkib, had ketepatan telah diturunkan kerana kehadiran kes panggilan yang mungkin akan menjadikan masalah tidak dapat diselesaikan dengan ketepatan daripada 1e-7. Dalam dunia yang ideal, had tidak membenarkan kes sedemikian dan masih memerlukan ketepatan yang tinggi, jadi menyelesaikan masalah dengan beberapa pengoptimuman berangka am bukanlah mudah.)

Sekatan

• x mengandungi daripada 3 hingga 50 elemen termasuk.
• y mengandungi bilangan unsur yang sama dengan x.
• semua koordinat antara 0 dan 10 termasuk
• x dan y mentakrifkan poligon cembung dalam arah lawan jam.

asal dalam bahasa inggeris

Pernyataan masalah

Had masa ialah 4 saat.

Awak ada kek. Dilihat dari atas, kek adalah poligon cembung (tegas). Anda diberi koordinat bucunya dalam int[]sx dan y.

Anda mempunyai lima kawan. Anda kini ingin memotong kek menjadi enam keping kawasan yang sama (tetapi tidak semestinya bentuk yang sama). Sudah tentu, sesiapa sahaja boleh melakukannya dalam lima potong - tetapi hanya profesional sejati boleh melakukannya dalam tiga!

Cari tiga potongan garis lurus yang melalui titik yang sama yang memotong kek kepada enam bahagian yang sama besar. Kembalikan {x, y, d1, d2, d3}, dengan (x, y) ialah titik sepunya bagi tiga potong, dan d1, d2, d3 ialah arahnya dalam radian.

definisi

Kelas: CakeForSix
Kaedah: potong
Parameter: int[], int[] Pulangan: double[] Tandatangan kaedah: double[] cut(int[] x, int[] y)
(pastikan kaedah anda terbuka)

Nota
— Arah positif sepanjang paksi x ialah 0 (radian), arah positif sepanjang paksi y ialah pi/2 (radian).
— Potongan dalam arah d adalah sama dengan potongan arah pi*k+d untuk sebarang integer k.
— Anda boleh kembali mana-mana arah, ia tidak perlu dari [0,pi).
— Penggred akan mengira luas enam keping kek anda secara beregu. Jawapan akan diterima jika perbezaan relatif atau mutlak antara mereka adalah kurang daripada 10^(-4).
— Lebih tepat lagi, biarkan X dan Y menjadi yang terkecil dan terbesar daripada enam kawasan anda, seperti yang dikira oleh penggred. Kemudian, jawapan anda akan diterima jika Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Versi asal masalah menggunakan ketepatan 1e-7 dan bukannya 1e-4. Untuk menyelesaikan masalah ini dalam arkib had ketepatan telah diturunkan kerana kewujudan kes cabaran yang berkemungkinan besar menjadikan tugas itu tidak dapat diselesaikan dengan ketepatan 1e-7 Dalam dunia yang ideal, kekangan tidak akan membenarkan kes sedemikian dan masih memerlukan ketepatan yang tinggi, supaya tidak mudah untuk menyelesaikan masalah melalui beberapa pengoptimuman berangka umum.)

Kekangan
— x akan mempunyai antara 3 dan 50 elemen, termasuk.
— y akan mempunyai bilangan elemen yang sama dengan x.
— Semua koordinat adalah antara 0 dan 10,000, termasuk.
— x dan y akan menerangkan poligon cembung mengikut tertib lawan jam.

contoh

0)

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
pulangan:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Heksagon simetri tetapi tidak sekata. Contoh jawapan sepadan dengan memotongnya separuh secara mendatar dan membuat dua potongan lain di tengah yang membahagikan setiap bahagian kepada tiga bahagian.

1)

{0, 1000, 0}
{0, 0, 1000}
pulangan:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Segitiga kanan. Sekali lagi, kita boleh mulakan dengan satu daripada tiga potongan di sepanjang paksi simetri.

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
pulangan:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

pentagon tidak teratur.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Pulangan: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

Sebuah segi empat sama berputar 45 darjah.

[Source]

Hanya pengguna berdaftar boleh mengambil bahagian dalam tinjauan. Log masuk, Sama-sama.

Saya menyelesaikan masalah untuk

• dalam masa kurang dari 10 minit

• minit 10-30

• minit 30-60

• jam 1-2

• dalam masa lebih 2 jam

• lain

42 pengguna telah mengundi. 47 pengguna berpantang.

Sumber: www.habr.com