По стъпките Публикувам задачи от направлението „Алгоритъм“. (Класическо състезателно програмиране. Трябва да решите три задачи на Java, C#, C++ или Python за час и половина.)
1. Пай за шестима
Проблем изявление
Времеви лимит: 4 секунди.
Имате пай. Погледнат отгоре, пайът има формата на (строго) изпъкнал многоъгълник. Дадени са ви целочислените координати на върховете, X и Y.
Имаш петима приятели. Искаш да разделиш пай на шест равни по размер парчета (но не непременно с еднаква форма). Разбира се, всеки може да го направи с пет разреза, но само професионалист може да го направи с три.
Намерете три разреза с прави линии, преминаващи през обща точка, които разделят пая на шест равни части. Изпишете {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 са ъглите на разрезите в радиани.
дефиницияКлас: CakeForSix
Метод: изрязване
Параметри: int[], int[]
Връща: double[]
Сигнатура на метода: double[] cut(int[] x, int[] y)
(уверете се, че методът ви е публичен)
Бележки
- Положителната посока по оста x е 0 (радиани), положителната посока по оста y е pi/2 (радиани).
- Разрезът в посока d е аналогичен на разреза в посока pi*k+d за всяко цяло число k.
- Можете да изведете произволни посоки, не е задължително да са от [0, пи).
- Оценщият ще изчисли площите на шестте парчета торта по двойки. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 10^(-4).
- По-точно, нека X и Y са най-малката и най-голямата от шестте ви площи, изчислени от оценяващия. Тогава отговорът ви ще бъде приет, ако Y
- (Оригиналната версия на задачата използваше точност 1e-7 вместо 1e-4. За да се реши този проблем, ограничението на точността беше намалено в архива поради наличието на случаи на извикване, които вероятно правят проблема неразрешим с точност 1e-7. В идеален свят ограниченията предотвратяват такива случаи и все още изискват висока точност, така че решаването на проблема с някаква обща числена оптимизация не е лесно.)
Ограничения
- x съдържа от 3 до 50 елемента включително.
- y съдържа същия брой елементи като x.
- всички координати между 0 и 10 000 включително
- x и y определят изпъкнал многоъгълник в посока обратна на часовниковата стрелка.
Оригинал на английски език
Декларация за проблема
Времето е 4 секунди.
Имате торта. Погледната отгоре, тортата е (строго) изпъкнал многоъгълник. Дадени са ви координатите на върховете му в int[]sx и y.
Имаш петима приятели. Сега искаш да разрежеш тортата на шест парчета с еднаква площ (но не непременно с еднаква форма). Разбира се, всеки може да направи това с пет разреза - но само истински професионалист може да го направи с три!
Намерете три праволинейни разреза, преминаващи през една и съща точка, които разрязват тортата на шест еднакво големи части. Върнете {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 са техните посоки в радиани.
дефиниция
Клас: CakeForSix
Метод: изрязване
Параметри: int[], int[]
Връща: double[]
Сигнатура на метода: double[] cut(int[] x, int[] y)
(уверете се, че методът ви е публичен)
бележки
— Положителната посока по оста x е 0 (радиана), положителната посока по оста y е π/2 (радиана).
— Разрез в посока d е същият като разрез в посока pi*k+d за всяко цяло число k.
— Можете да върнете произволни посоки, те не е задължително да са от [0,пи).
— Оценщият ще изчисли площите на шестте парчета торта по двойки. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 10^(-4).
— По-точно, нека X и Y са най-малката и най-голямата от шестте ви области, изчислени от оценяващия. Тогава отговорът ви ще бъде приет, ако Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Оригиналната версия на задачата използваше точност 1e-7 вместо 1e-4. За решаването на тази задача в архива ограничението на точността беше намалено поради наличието на трудни случаи, които най-вероятно правят задачата неразрешима с точност 1e-7. В идеален свят ограниченията не биха позволили такива случаи и все пак биха изисквали висока точност, така че не е лесно да се реши задачата чрез някаква обща числена оптимизация.)
Ограничения
— x ще има между 3 и 50 елемента, включително.
— y ще има същия брой елементи като x.
— Всички координати ще бъдат между 0 и 10 000 включително.
— x и y ще опишат изпъкнал многоъгълник в ред обратно на часовниковата стрелка.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Рекламации:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}
Симетричен, но неправилен шестоъгълник. Примерният отговор съответства на разрязването му наполовина хоризонтално и направата на два други разреза по центъра, като всяка половина се разделя на три.
1)
{0, 1000, 0}
{0, 0, 1000}
Рекламации:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753}
Правоъгълен триъгълник. Отново можем да започнем с един от трите разреза по оста на симетрия.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Рекламации:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475}
Неправилен петоъгълник.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Връщания: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Квадрат, завъртян на 45 градуса.
[]
В анкетата могат да участват само регистрирани потребители. , Моля те.
Реших проблема в
за по -малко от 10 минути
10 30-та
30 60-та
1-2 часа
повече от 2 часа
друг
42 потребители гласуваха. 47 потребители се въздържаха.
Източник: www.habr.com
