По стъпките Публикувам задачи от пистата Алгоритъм (класическо спортно програмиране. За час и половина трябва да решите три задачи на 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, pi).
- Градерът ще изчисли площта на вашите шест парчета торта на двойки. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 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 е 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 XNUMX включително.
— 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