I fodsporene Jeg udgiver problemer fra Algoritme-sporet (klassisk sportsprogrammering. På halvanden time skal du løse tre opgaver i Java, C#, C++ eller Python.)
1. Tærte til seks
Formulering af problemet
Tidsgrænsen er 4 sekunder.
Du har en tærte. Set fra oven har kagen form af en (strengt) konveks polygon. Du får koordinaterne for hjørnerne i X- og Y-heltal.
Du har fem venner. Du vil dele tærten i seks stykker med lige store areal (men ikke nødvendigvis samme form). Selvfølgelig kan alle gøre det i fem snit, men kun en professionel kan gøre det i tre snit.
Find tre udskæringer i lige linjer gennem et punkt, der deler tærten i seks lige store dele. Udskriv {x, y, d1, d2, d3}, hvor (x, y) er fællespunktet for alle tre snit, og d1, d2, d3 er retningsvinklerne for snittene i radianer.
DefinitionKlasse: CakeForSix
Metode: klip
Parametre: int[], int[] Returnerer: double[] Metodesignatur: double[] cut(int[] x, int[] y)
(sørg for, at din metode er offentlig)
noter
- Den positive retning langs x-aksen er 0 (radianer), den positive retning langs y-aksen er pi/2 (radianer).
- Et snit i d-retningen svarer til et snit i pi*k+d-retningen for ethvert heltal k.
- Du kan udskrive alle retninger, de behøver ikke at være fra [0, pi).
- Graderen vil beregne arealet af dine seks kagestykker i dobbelte. Svaret vil blive accepteret, hvis den relative eller absolutte forskel mellem dem er mindre end 10^(-4).
- Mere præcist, lad X og Y være den mindste og største af dine seks områder beregnet af graderen. Så vil dit svar blive accepteret, hvis Y
- (Den originale version af problemet brugte en præcision på 1e-7 i stedet for 1e-4. For at løse dette problem i arkivet blev præcisionsgrænsen sænket på grund af tilstedeværelsen af opkaldssager, der sandsynligvis ville gøre problemet uløseligt med en præcision af 1e-7. I en ideel verden tillader grænserne ikke sådanne tilfælde og kræver stadig høj præcision, så det er ikke let at løse problemet med en vis generel numerisk optimering.)
Begrænsninger
- x indeholder fra 3 til 50 elementer inklusive.
- y indeholder det samme antal elementer som x.
- alle koordinater mellem 0 og 10 inklusive
- x og y definerer en konveks polygon i retning mod uret.
Original på engelsk
Problemformulering
Tidsgrænsen er 4 sekunder.
Du har en kage. Set fra oven er kagen en (strengt) konveks polygon. Du får givet koordinaterne for dets hjørner i int[]sx og y.
Du har fem venner. Du vil nu skære kagen i seks stykker med lige store areal (men ikke nødvendigvis lige form). Selvfølgelig kan enhver gøre det i fem snit - men kun en ægte professionel kan gøre det på tre!
Find tre lige snit, der går gennem det samme punkt, som skærer kagen i seks lige store dele. Returner {x, y, d1, d2, d3}, hvor (x, y) er det fælles punkt for de tre snit, og d1, d2, d3 er deres retninger i radianer.
Definition
Klasse: CakeForSix
Metode: klip
Parametre: int[], int[] Returnerer: double[] Metodesignatur: double[] cut(int[] x, int[] y)
(sørg for, at din metode er offentlig)
Noter
— Den positive retning langs x-aksen er 0 (radianer), den positive retning langs y-aksen er pi/2 (radianer).
— Et snit i retning d er det samme som et snit i retning pi*k+d for ethvert heltal k.
— Du kan returnere alle retninger, de behøver ikke at være fra [0,pi).
— Gradatoren beregner arealerne af dine seks kagestykker dobbelt. Svaret vil blive accepteret, hvis den relative eller absolutte forskel mellem dem er mindre end 10^(-4).
— Mere præcist, lad X og Y være den mindste og den største af dine seks områder, som beregnet af graderen. Derefter vil dit svar blive accepteret, hvis Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Den originale version af problemet brugte 1e-7-præcision i stedet for 1e-4. For at løse dette problem i arkivet blev præcisionsgrænsen sænket på grund af eksistensen af udfordringstilfælde, der højst sandsynligt gør opgaven uløselig med 1e-7-præcision I en ideel verden ville begrænsningerne ikke tillade sådanne tilfælde og stadig kræve høj præcision, så det er ikke let at løse problemet via en generel numerisk optimering.)
Begrænsninger
— x vil have mellem 3 og 50 elementer inklusive.
— y vil have det samme antal elementer som x.
— Alle koordinater vil være mellem 0 og 10,000 inklusive.
— x og y vil beskrive en konveks polygon i rækkefølge mod uret.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returret:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
En symmetrisk, men uregelmæssig sekskant. Eksempelsvaret svarer til at skære det i halve vandret og lave to andre snit ned i midten, der deler hvert stykke i tre dele.
1)
{0, 1000, 0}
{0, 0, 1000}
Returret:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
retvinklet trekant. Igen kan vi starte med et af tre snit langs symmetriaksen.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returret:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Uregelmæssig femkant.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returneringer: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
En firkant roteret 45 grader.
[]
Kun registrerede brugere kan deltage i undersøgelsen. , Vær venlig.
Jeg løste problemet for
-
på mindre end 10 minutter
-
10-30 minutter
-
30-60 minutter
-
1-2 timer
-
på mere end 2 timer
-
andre
42 brugere stemte. 47 brugere undlod at stemme.
Kilde: www.habr.com