Па следам публікую задачы з трэка Algorithm (класічнае спартовае праграмаванне. За паўтары гадзіны трэба вырашыць тры задачы на Java, C#, C++ ці Python.)
1. Пірог на шасцярых
Пастаноўка задачы
Ліміт часу - 4 секунды.
У вас ёсць пірог. Калі глядзець зверху, пірог мае форму (строга) выпуклага шматкутніка. Вам дадзены каардынаты вяршыняў у цэлых ліках X і Y.
У вас ёсць пяць сяброў. Вы жадаеце падзяліць пірог на шэсць частак роўнага пляца (але не абавязкова аднолькавай формы). Вядома ж, любы можа гэта зрабіць за пяць разрэзаў, але толькі профі можа зрабіць гэта за тры разрэзы.
Знайдзіце тры разразанні прамымі лініямі праз адзін пункт, якія падзеляць пірог на шэсць роўных па плошчы частак. Вывядзіце {x, y, d1, d2, d3}, дзе (x, y) — агульны пункт усіх трох разрэзаў, а d1, d2, d3 — вуглы напрамку разрэзаў у радыянах.
ВызначэннеClass: CakeForSix
Method: cut
Parameters: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(be sure your method is public)
Заўвагі
- Дадатны кірунак уздоўж восі х роўна 0 (радыян), дадатны кірунак уздоўж восі y роўна pi/2 (радыян).
- Разрэз у напрамку d аналагічны разрэзу ў напрамку pi*k+d для любога цэлага ліку k.
- Вы можаце вывесці любыя кірункі, яны не абавязкова павінны быць ад [0, pi).
- Грэйдэр вылічыць плошчы вашых шасці кавалачкаў торта ў doubles. Адказ будзе прыняты, калі адносная або абсалютная розніца паміж імі меншая за 10^(-4).
- Дакладней, няхай X і Y будуць самымі маленькімі і самымі вялікімі з вашых шасці абласцей, вылічаных грэйдэрам. Тады ваш адказ будзе прыняты, калі Y
- (У першапачатковай версіі задачы выкарыстоўвалася дакладнасць 1e-7 замест 1e-4. Для вырашэння гэтай праблемы ў архіве мяжа дакладнасці была зніжана з-за наяўнасці выпадкаў выкліку, якія, хутчэй за ўсё, робяць задачу невырашальнай з дакладнасцю 1e-7. У ідэальным свеце абмежаванні не дапускаюць такіх выпадкаў і ўсё яшчэ патрабуюць высокай дакладнасці, так што вырашыць праблему з дапамогай некаторай агульнай лікавой аптымізацыі няпроста.)
Абмежаванні
- x змяшчае ад 3 да 50 элементаў уключна.
- y змяшчае столькі ж элементаў, што і x.
- усе каардынаты паміж 0 і 10 000 уключна
- x і y задаюць выпуклы шматкутнік у напрамку супраць гадзіннікавай стрэлкі.
Арыгінал на англійскай
Пастаноўка праблемы
Time limit is 4 seconds.
Вы будзеце мець. Сене з таго, што tortu — (strictly) convex polygon. Вы мусіце кіраваць сваімі vertices ў int[]sx and y.
Вы маеце XNUMX friends. Вы ведаеце, што цапяць у XNUMX кірунках экв. З course, anyone can do that in five cuts — but only a true pro can do it in three!
Find three straight-line cuts passing through same point that cut the cake in six equally large parts. Адварот {x, y, d1, d2, d3}, дзе (x, y) з'яўляецца адным пунктам трох крэсаў, і d1, d2, d3 ёсць свае адносіны ў radians.
Вызначэнне
Class: CakeForSix
Method: cut
Parameters: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(be sure your method is public)
нататкі
- Пазітыўны акцэнт уздоўж x axis 0 (radians), positive direction па the y axis is pi/2 (radians).
— А cut in direction d is the same as cut in direction pi*k+d для любога integer k.
- Вы павінны адправіць любыя directions, яны не павінны быць ад [0,pi).
- Рыхтар будзе складаць раёны сваіх шасці tort pieces in doubles. Лічыцца, што яна будзе прыемна, калі адносна або цалкам адпавядае паміж тым, што не так, як 10^(-4).
- Больш за тое, што X і Y, каб быць нязначным і вялікім шасці шасці зон, а computed by grader. Then, your answer will be accepted if Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Гэта арыенцірная версія пытання, выкарыстаная 1e-7 precision instead of 1e-4. Для паляпшэння гэтага пытання ў архіве, узровень ліміту была задаволена да таго, што існуюць парушэнні выпадкаў, якія most likely make the task unsolvable with 1e-7 precision У сучасным свеце навакольных не можа не таку цану і не патрабуецца высокая ўпэўненасць, так што гэта не можа быць вельмi простым, каб вырашыць пытанне ў некаторых нумеравае optimization.)
Constraints
- x will have between 3 and 50 elements, inclusive.
- y will have the same number of elements as x.
- All coordinates will be between 0 and 10,000, inclusive.
- x and y will напісана з convex polygon ў counterclockwise order.
прыклады
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}
Returns: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
Квадрат, звернуты на 45 градусаў.
[]
Толькі зарэгістраваныя карыстачы могуць удзельнічаць у апытанні. , Калі ласка.
Я вырашыў задачу за
-
менш чым за 10 хвілін
-
10-30 хвілін
-
30-60 хвілін
-
1-2 гадзіны
-
больш чым за 2 гадзіны
-
іншае
Прагаласавалі 42 карыстальніка. Устрымаліся 47 карыстальнікаў.
Крыніца: habr.com