Di jalan Saya mempublikasikan masalah dari jalur Algoritma (pemrograman olahraga klasik. Dalam satu setengah jam Anda perlu menyelesaikan tiga masalah di Java, C#, C++, atau Python.)
1. Pai untuk enam orang
Pernyataan masalah
Batas waktunya adalah 4 detik.
Anda punya kue. Jika dilihat dari atas, kue tersebut berbentuk poligon (tepat) cembung. Anda diberikan koordinat simpul dalam bilangan bulat X dan Y.
Anda memiliki lima teman. Anda ingin membagi pai menjadi enam bagian dengan luas yang sama (tetapi bentuknya tidak harus sama). Tentu saja, siapa pun dapat melakukannya dalam lima pemotongan, tetapi hanya seorang profesional yang dapat melakukannya dalam tiga pemotongan.
Temukan tiga potongan garis lurus melalui satu titik yang akan membagi kue menjadi enam bagian yang sama. Cetak {x, y, d1, d2, d3}, dengan (x, y) adalah titik persekutuan ketiga potongan, dan d1, d2, d3 adalah sudut arah potongan dalam radian.
DefinisiKelas: CakeForSix
Metode: potong
Parameter: int[], int[] Pengembalian: double[] Tanda tangan metode: double[] cut(int[] x, int[] y)
(pastikan metode Anda bersifat publik)
Catatan
- Arah positif sepanjang sumbu x adalah 0 (radian), arah positif sepanjang sumbu y adalah pi/2 (radian).
- Pemotongan pada arah d serupa dengan pemotongan pada arah pi*k+d untuk sembarang bilangan bulat k.
- Anda dapat menampilkan arah mana pun, tidak harus dari [0, pi).
- Siswa kelas akan menghitung luas enam potong kue Anda secara ganda. Jawaban diterima jika selisih relatif atau mutlak di antara keduanya kurang dari 10^(-4).
- Lebih tepatnya, misalkan X dan Y adalah luas terkecil dan terbesar dari enam luas yang dihitung oleh penilai. Maka jawaban anda akan diterima jika Y
- (Versi asli dari soal menggunakan presisi 1e-7, bukan 1e-4. Untuk menyelesaikan masalah ini di arsip, batas presisi diturunkan karena adanya kasus pemanggilan yang kemungkinan akan membuat masalah tidak dapat diselesaikan dengan presisi dari 1e-7. Dalam dunia yang ideal, batasannya tidak memungkinkan terjadinya kasus seperti itu dan masih memerlukan presisi tinggi, sehingga menyelesaikan masalah dengan beberapa optimasi numerik umum tidaklah mudah.)
Pembatasan
- x berisi 3 hingga 50 elemen inklusif.
- y mengandung jumlah elemen yang sama dengan x.
- semua koordinat antara 0 dan 10 inklusif
- x dan y mendefinisikan poligon cembung dengan arah berlawanan jarum jam.
Asli dalam bahasa Inggris
Pernyataan Masalah
Batas waktu adalah 4 detik.
Anda punya kue. Dilihat dari atas, kuenya berbentuk poligon (tepatnya) cembung. Anda diberikan koordinat simpulnya di int[]sx dan y.
Anda memiliki lima teman. Anda sekarang ingin memotong kue menjadi enam bagian dengan luas yang sama (tetapi bentuknya tidak harus sama). Tentu saja, siapa pun dapat melakukannya dalam lima potongan — tetapi hanya seorang profesional sejati yang dapat melakukannya dalam tiga potongan!
Temukan tiga potongan garis lurus melalui titik yang sama yang memotong kue menjadi enam bagian yang sama besarnya. Kembalikan {x, y, d1, d2, d3}, dengan (x, y) adalah titik persekutuan dari ketiga potongan, dan d1, d2, d3 adalah arahnya dalam radian.
Definisi
Kelas: CakeForSix
Metode: potong
Parameter: int[], int[] Pengembalian: double[] Tanda tangan metode: double[] cut(int[] x, int[] y)
(pastikan metode Anda bersifat publik)
Catatan
— Arah positif sepanjang sumbu x adalah 0 (radian), arah positif sepanjang sumbu y adalah pi/2 (radian).
— Pemotongan dalam arah d sama dengan pemotongan dalam arah pi*k+d untuk sembarang bilangan bulat k.
— Anda dapat mengembalikan arah mana pun, tidak harus dari [0,pi).
— Siswa kelas akan menghitung luas enam potong kue Anda secara ganda. Jawaban diterima jika selisih relatif atau mutlak di antara keduanya kurang dari 10^(-4).
— Lebih tepatnya, misalkan X dan Y adalah luas terkecil dan terbesar dari enam luas yang dihitung oleh penilai. Maka jawabanmu diterima jika Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Versi asli dari soal menggunakan presisi 1e-7, bukan 1e-4. Untuk menyelesaikan masalah ini di arsip, batas presisi diturunkan karena adanya kasus tantangan yang kemungkinan besar membuat tugas tidak dapat diselesaikan dengan presisi 1e-7 Dalam dunia ideal, batasan tidak memungkinkan terjadinya kasus seperti itu dan masih memerlukan presisi tinggi, sehingga tidak mudah menyelesaikan masalah melalui optimasi numerik umum.)
kendala
— x akan memiliki antara 3 dan 50 elemen, inklusif.
— y akan memiliki jumlah elemen yang sama dengan x.
— Semua koordinat akan berada di antara 0 dan 10,000, inklusif.
— x dan y akan menggambarkan poligon cembung dalam urutan berlawanan arah jarum jam.
contoh
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Pengembalian:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Segi enam simetris namun tidak beraturan. Contoh jawabannya adalah dengan memotongnya menjadi dua secara horizontal dan membuat dua potongan lainnya di tengah yang membagi setiap bagian menjadi tiga bagian.
1)
{0, 1000, 0}
{0, 0, 1000}
Pengembalian:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Segitiga siku-siku. Sekali lagi, kita bisa mulai dengan salah satu dari tiga potongan sepanjang sumbu simetri.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Pengembalian:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
segi lima tidak beraturan.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Pengembalian: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Sebuah persegi diputar 45 derajat.
[]
Hanya pengguna terdaftar yang dapat berpartisipasi dalam survei. , silakan.
Saya memecahkan masalah untuk
-
dalam waktu kurang dari 10 menit
-
10-30 menit
-
30-60 menit
-
Jam 1-2
-
dalam waktu lebih dari 2 jam
-
lain
42 pengguna memilih. 47 pengguna abstain.
Sumber: www.habr.com