По стъпките публикувам задачи от трека Algorithm (класическо спортно програмиране. За един час и половина трябва да решите три задачи на Java, C#, C++ или Python.)
1. Пирогът за шестима
Формулиране на задачата
Времевият лимит е 4 секунди.
Имате пирог. Когато го погледнете отгоре, той има формата на (строго) изпъкнал многоъгълник. Дадени са ви координатите на върховете в цели числа X и Y.
Имаме пет приятели. Искате да разделите пирога на шест части с равна площ (но не задължително с еднаква форма). Разбира се, всеки може да го направи с пет разреза, но само професионалист може да го направи с три разреза.
Намерете три разреза с прави линии през една точка, които да разделят пирога на шест равни по площ части. Изведете {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 — ъглите на разрезите в радиани.
ОпределениеКлас: CakeForSix
Метод: cut
Параметри: int[], int[]
Връща: double[]
Подпис на метода: double[] cut(int[] x, int[] y)
(убедете се, че вашият метод е публичен)
Забележки
- Положителната посока по оста x е равна на 0 (радиани), положителната посока по оста y е равна на pi/2 (радиани).
- Разрезът в посока d е подобен на разреза в посока pi*k+d за всяко цяло число k.
- Можете да извеждате всякакви посоки, те не е задължително да са от [0, pi).
- Грейдерът ще изчисли площите на вашите шест парчета торта в doubles. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 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 задават изпъкнал многоъгълник в посока против часовниковата стрелка.
Оригинал на английски
Задание на проблема
Времевият лимит е 4 секунди.
Имате торта. Гледайки отгоре, тортът е (строго) конвексен многоъгълник. Дадени са координатите на върховете му в int[] масиви x и y.
Имате пет приятели. Сега искате да нарежете тортата на шест парчета с еднаква площ (но не непременно с равна форма). Разбира се, всеки може да го направи с пет разреза — но само истински професионалист може да го направи с три!
Намерете три прави разреза, минаващи през същата точка, които разрязват тортата на шест равни части. Върнете {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 са техните направления в радиани.
Определение
Клас: CakeForSix
Метод: cut
Параметри: int[], int[]
Връща: double[]
Подпис на метода: double[] cut(int[] x, int[] y)
(убедете се, че вашият метод е публичен)
Бележки
— Положителното направление по оста x е 0 (радиани), положителното направление по оста y е pi/2 (радиани).
— Разрез в направление d е същият като разрез в направление pi*k+d за всяко цяло число k.
— Можете да върнете всякакви направления, те не трябва да бъдат от [0,pi).
— Оценчикът ще изчисли площите на вашите шест парчета торта в двойни стойности. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 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 потребителя.
Източник: habr.com
