En la paŝoj Mi publikigas problemojn de la Algoritmo-trako (klasika sporta programado. En unu kaj duona horo oni devas solvi tri problemojn en Java, C#, C++ aŭ Python.)
1. Torto por ses
Formulado de la problemo
La tempolimo estas 4 sekundoj.
Vi havas torton. Se rigardita de supre, la kuko havas la formon de (strikte) konveksa plurlatero. Vi ricevas la koordinatojn de la verticoj en X kaj Y-entjeroj.
Vi havas kvin amikojn. Vi volas dividi la kukaĵon en ses pecojn de egala areo (sed ne nepre la sama formo). Kompreneble, ĉiu povas fari ĝin en kvin tranĉoj, sed nur profesiulo povas fari ĝin en tri tranĉoj.
Trovu tri tranĉojn en rektaj linioj tra unu punkto, kiu dividos la kukaĵon en ses egalajn partojn. Print {x, y, d1, d2, d3}, kie (x, y) estas la komuna punkto de ĉiuj tri tranĉoj, kaj d1, d2, d3 estas la direktaj anguloj de la tranĉoj en radianoj.
difinonKlaso: CakeForSix
Metodo: tranĉi
Parametroj: int[], int[] Donas: double[] Metoda subskribo: double[] cut(int[] x, int[] y)
(certu, ke via metodo estas publika)
Notoj
- La pozitiva direkto laŭ la x-akso estas 0 (radianoj), la pozitiva direkto laŭ la y-akso estas pi/2 (radianoj).
- Tranĉo en la d-direkto estas simila al tranĉo en la pi*k+d-direkto por iu entjero k.
- Vi povas eligi iujn ajn direktojn, ili ne devas esti de [0, pi).
- La klasisto kalkulos la areon de viaj ses pecoj da kuko duoble. La respondo estos akceptita se la relativa aŭ absoluta diferenco inter ili estas malpli ol 10^(-4).
- Pli precize, X kaj Y estu la plej malgrandaj kaj plej grandaj el viaj ses areoj kalkulitaj de la klasisto. Tiam via respondo estos akceptita se Y
- (La originala versio de la problemo uzis precizecon de 1e-7 anstataŭ 1e-4. Por solvi ĉi tiun problemon en la arkivo, la precizeclimo estis malaltigita pro la ĉeesto de vokantaj kazoj kiuj verŝajne igus la problemon nesolvebla kun precizeco. de 1e-7. En ideala mondo, la limoj ne permesas tiajn kazojn kaj ankoraŭ postulas altan precizecon, do solvi la problemon per iu ĝenerala nombra optimumigo ne estas facila.)
Restriktoj
- x enhavas de 3 ĝis 50 elementoj inkluzive.
- y enhavas la saman nombron da elementoj kiel x.
- ĉiuj koordinatoj inter 0 kaj 10 inkluzive
- x kaj y difinas konveksan plurlaton en maldekstruma direkto.
Originalo en la angla
Problema Deklaro
Tempolimo estas 4 sekundoj.
Vi havas kukon. Vidita de supre, la kuko estas (strikte) konveksa plurlatero. Vi ricevas la koordinatojn de ĝiaj verticoj en la int[]sx kaj y.
Vi havas kvin amikojn. Vi nun volas tranĉi la kukon en ses pecojn de egala areo (sed ne nepre egala formo). Kompreneble, ĉiu povas fari tion en kvin tranĉoj - sed nur vera profesiulo povas fari ĝin en tri!
Trovu tri rektajn tranĉojn pasantajn tra la sama punkto, kiu tranĉis la kukon en ses same grandajn partojn. Reveno {x, y, d1, d2, d3}, kie (x, y) estas la komuna punkto de la tri tranĉoj, kaj d1, d2, d3 estas iliaj direktoj en radianoj.
difinon
Klaso: CakeForSix
Metodo: tranĉi
Parametroj: int[], int[] Donas: double[] Metoda subskribo: double[] cut(int[] x, int[] y)
(certu, ke via metodo estas publika)
Notoj
— La pozitiva direkto laŭ la x-akso estas 0 (radianoj), la pozitiva direkto laŭ la y-akso estas pi/2 (radianoj).
— Tranĉo en direkto d estas sama kiel tranĉo en direkto pi*k+d por iu entjero k.
— Vi povas redoni iujn ajn direktojn, ili ne devas esti de [0,pi).
— La klasisto kalkulos la areojn de viaj ses kukpecoj en duoble. La respondo estos akceptita se la relativa aŭ absoluta diferenco inter ili estas malpli ol 10^(-4).
— Pli precize, X kaj Y estu la plej malgrandaj kaj la plej grandaj el viaj ses areoj, kiel kalkulitaj de la klasisto. Tiam, via respondo estos akceptita se Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (La originala versio de la problemo uzis 1e-7 precizecon anstataŭ 1e-4. Por solvi ĉi tiun problemon en la arkivo la precizeclimo estis malaltigita pro la ekzisto de defiokazoj kiuj plej verŝajne faras la taskon nesolvebla kun 1e-7 precizeco. En ideala mondo la limoj ne permesus tiajn kazojn kaj ankoraŭ postulus altan precizecon, tiel ke ne estas facile solvi la problemon per iu ĝenerala nombra optimumigo.)
Limigoj
— x havos inter 3 kaj 50 elementojn, inkluzive.
— y havos la saman nombron da elementoj kiel x.
— Ĉiuj koordinatoj estos inter 0 kaj 10,000, inkluzive.
— x kaj y priskribos konveksan plurlaton en maldekstruma ordo.
ekzemploj
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Redaktoj:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}
Simetria sed neregula heksagono. La ekzempla respondo respondas al tranĉi ĝin en duono horizontale kaj fari du aliajn tranĉojn laŭ la centro, kiuj dividas ĉiun pecon en tri partojn.
1)
{0, 1000, 0}
{0, 0, 1000}
Redaktoj:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753}
Orta triangulo. Denove, ni povas komenci per unu el tri tranĉoj laŭ la simetria akso.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Redaktoj:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475}
Neregula kvinangulo.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Revenoj: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
Kvadrato turniĝis 45 gradojn.
[]
Nur registritaj uzantoj povas partopreni la enketon. , bonvolu.
Mi solvis la problemon por
-
en malpli ol 10 minutoj
-
10-30 minutoj
-
30-60 minutoj
-
1-2 horoj
-
en pli ol 2 horoj
-
alia
42 uzantoj voĉdonis. 47 uzantoj sindetenis.
fonto: www.habr.com