Izdan Men muammolarni Algoritm trekidan nashr qilaman (Klassik sport dasturlari. Bir yarim soat ichida Java, C#, C++ yoki Python tillarida uchta masalani yechish kerak.)
1. Olti kishilik pirog
Muammoni shakllantirish
Vaqt chegarasi 4 soniya.
Sizda pirog bor. Yuqoridan qaralganda, kek (qat'iy) konveks ko'pburchak shakliga ega. Sizga X va Y butun sonlarda cho'qqilarning koordinatalari berilgan.
Sizning beshta do'stingiz bor. Siz pirogni oltita teng maydonga bo'lishni xohlaysiz (lekin bir xil shaklda bo'lishi shart emas). Albatta, har kim buni beshta kesishda qila oladi, lekin faqat professional buni uchta kesishda qila oladi.
Pirogni oltita teng qismga bo'ladigan bitta nuqtadan uchta to'g'ri chiziqni toping. Chop etish {x, y, d1, d2, d3}, bu yerda (x, y) har uchala kesmaning umumiy nuqtasi, d1, d2, d3 esa kesmalarning radiandagi yo‘nalish burchaklaridir.
aniqlashSinf: CakeForSix
Usul: kesish
Parametrlar: int[], int[] Qaytadi: double[] Usul imzosi: double[] cut(int[] x, int[] y)
(usulingiz ommaviy ekanligiga ishonch hosil qiling)
Eslatmalar
- X o'qi bo'ylab ijobiy yo'nalish 0 (radian), y o'qi bo'ylab musbat yo'nalish pi/2 (radian).
- d yo'nalishidagi kesim har qanday k butun soni uchun pi*k+d yo'nalishidagi kesimga o'xshaydi.
- Siz istalgan yo'nalishni chiqarishingiz mumkin, ular [0, pi) dan bo'lishi shart emas.
- Greyder sizning olti bo'lak kekingizning maydonini ikki marta hisoblab chiqadi. Agar ular orasidagi nisbiy yoki mutlaq farq 10^(-4) dan kam bo‘lsa, javob qabul qilinadi.
- Aniqroq qilib aytganda, X va Y greyder tomonidan hisoblangan oltita hududingizning eng kichiki va eng kattasi bo'lsin. Agar Y bo'lsa, javobingiz qabul qilinadi
- (Muammoning asl versiyasida 1e-7 oʻrniga 1e-4 aniqligi ishlatilgan. Arxivdagi bu muammoni hal qilish uchun muammoni aniqlik bilan hal qilib boʻlmaydigan qilib qoʻyadigan chaqiruv holatlari mavjudligi sababli aniqlik chegarasi pasaytirildi. 1e-7. Ideal dunyoda chegaralar bunday holatlarga yo'l qo'ymaydi va hali ham yuqori aniqlikni talab qiladi, shuning uchun muammoni ba'zi umumiy raqamli optimallashtirish bilan hal qilish oson emas.)
Cheklovlar
- x 3 dan 50 tagacha elementni o'z ichiga oladi.
- y x bilan bir xil miqdordagi elementlarni o'z ichiga oladi.
- 0 dan 10 000 gacha bo'lgan barcha koordinatalar
- x va y soat miliga teskari yo'nalishda qavariq ko'pburchakni aniqlaydi.
Ingliz tilida asl
Muammo bayonoti
Vaqt chegarasi 4 soniya.
Sizda tort bor. Yuqoridan ko'rinib turibdiki, kek (qat'iy) konveks ko'pburchakdir. Sizga int[]sx va y da uning uchlari koordinatalari berilgan.
Sizning beshta do'stingiz bor. Endi siz tortni oltita teng bo'lakka kesib olishni xohlaysiz (lekin bir xil shaklda bo'lishi shart emas). Albatta, har kim buni beshta kesishda qila oladi - lekin faqat haqiqiy professional buni uchtada qila oladi!
Kekni oltita teng katta qismga bo'lgan bir xil nuqtadan o'tadigan uchta to'g'ri chiziqni toping. Qaytish {x, y, d1, d2, d3}, bu erda (x, y) - uchta kesmaning umumiy nuqtasi va d1, d2, d3 - ularning radiandagi yo'nalishlari.
aniqlash
Sinf: CakeForSix
Usul: kesish
Parametrlar: int[], int[] Qaytadi: double[] Usul imzosi: double[] cut(int[] x, int[] y)
(usulingiz ommaviy ekanligiga ishonch hosil qiling)
Eslatmalar
— X o'qi bo'ylab musbat yo'nalish 0 (radian), y o'qi bo'ylab musbat yo'nalish pi/2 (radian).
— d yo‘nalishidagi kesim har qanday k butun soni uchun pi*k+d yo‘nalishidagi kesma bilan bir xil bo‘ladi.
— Siz istalgan yoʻnalishni qaytarishingiz mumkin, ular [0,pi] dan boʻlishi shart emas.
- Greyder sizning oltita pirojnoe bo'lagining maydonlarini juftlikda hisoblab chiqadi. Agar ular orasidagi nisbiy yoki mutlaq farq 10^(-4) dan kam bo‘lsa, javob qabul qilinadi.
— Aniqrogʻi, X va Y greyder tomonidan hisoblangan oltita hududingizning eng kichiki va eng kattasi boʻlsin. Agar Y < max( X + 10^(-4), X * (1+10^(-4)) boʻlsa, javobingiz qabul qilinadi.
— (Muammoning asl nusxasida 1e-7 oʻrniga 1e-4 aniqligi ishlatilgan. Arxivdagi ushbu muammoni hal qilish uchun aniqlik chegarasi 1e-7 aniqligi bilan vazifani hal qilib boʻlmaydigan qilib qoʻyish holatlari mavjudligi sababli pasaytirildi. Ideal dunyoda cheklovlar bunday holatlarga yo'l qo'ymaydi va hali ham yuqori aniqlikni talab qiladi, shuning uchun muammoni umumiy raqamli optimallashtirish orqali hal qilish oson emas.)
Cheklovlar
— x 3 dan 50 tagacha elementga ega bo'ladi, shu jumladan.
— y ning elementlari soni x bilan bir xil bo‘ladi.
— Barcha koordinatalar 0 dan 10,000 XNUMX gacha, shu jumladan.
- x va y qavariq ko'pburchakni soat miliga teskari tartibda tasvirlaydi.
misollar
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Qaytadi:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Nosimmetrik, lekin tartibsiz olti burchakli. Misol javobi, uni gorizontal ravishda yarmiga bo'lish va har bir bo'lakni uchta bo'lakka bo'ladigan markazdan ikkita boshqa kesma qilish bilan mos keladi.
1)
{0, 1000, 0}
{0, 0, 1000}
Qaytadi:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
To'g'ri uchburchak. Shunga qaramay, biz simmetriya o'qi bo'ylab uchta kesishdan birini boshlashimiz mumkin.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Qaytadi:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Noto'g'ri beshburchak.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Qaytishlar: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat 45 daraja aylantirildi.
[]
So'rovda faqat ro'yxatdan o'tgan foydalanuvchilar ishtirok etishlari mumkin. iltimos.
uchun muammoni hal qildim
-
10 daqiqadan kamroq vaqt ichida
-
10-30 daqiqa
-
30-60 daqiqa
-
1-2 soat
-
2 soatdan ko'proq vaqt ichida
-
boshqa
42 foydalanuvchi ovoz berdi. 47 nafar foydalanuvchi betaraf qoldi.
Manba: www.habr.com