I fotspåren Jag publicerar problem från Algoritm-spåret (klassisk sportprogrammering. På en och en halv timme behöver du lösa tre problem i Java, C#, C++ eller Python.)
1. Paj för sex
Problem uttalande
Tidsgränsen är 4 sekunder.
Du har en paj. När den ses ovanifrån har kakan formen av en (strängt) konvex polygon. Du får koordinaterna för hörnen i X- och Y-heltal.
Du har fem vänner. Du vill dela pajen i sex bitar med lika stor yta (men inte nödvändigtvis samma form). Naturligtvis kan vem som helst göra det i fem snitt, men bara ett proffs kan göra det i tre snitt.
Hitta tre raka linjer genom en punkt som delar pajen i sex lika stora delar. Skriv ut {x, y, d1, d2, d3}, där (x, y) är den gemensamma punkten för alla tre snitt, och d1, d2, d3 är riktningsvinklarna för snitten i radianer.
DefinitionKlass: CakeForSix
Metod: skär
Parametrar: int[], int[] Returnerar: double[] Metodsignatur: double[] cut(int[] x, int[] y)
(se till att din metod är offentlig)
Anteckningar
- Den positiva riktningen längs x-axeln är 0 (radianer), den positiva riktningen längs y-axeln är pi/2 (radianer).
- Ett snitt i d-riktningen liknar ett snitt i pi*k+d-riktningen för vilket heltal k som helst.
- Du kan mata ut vilka riktningar som helst, de behöver inte vara från [0, pi).
- Gradaren kommer att beräkna arean av dina sex tårtbitar i dubbel. Svaret kommer att accepteras om den relativa eller absoluta skillnaden mellan dem är mindre än 10^(-4).
- Närmare bestämt, låt X och Y vara de minsta och största av dina sex arealer beräknade av väghyveln. Då kommer ditt svar att accepteras om Y
- (Den ursprungliga versionen av problemet använde en precision på 1e-7 istället för 1e-4. För att lösa detta problem i arkivet sänktes precisionsgränsen på grund av förekomsten av anropsfall som sannolikt skulle göra problemet olösligt med en precision av 1e-7. I en idealisk värld tillåter inte gränserna sådana fall och kräver fortfarande hög precision, så att lösa problemet med någon allmän numerisk optimering är inte lätt.)
Begränsningar
- x innehåller från 3 till 50 element inklusive.
- y innehåller samma antal element som x.
- alla koordinater mellan 0 och 10 000 inklusive
- x och y definierar en konvex polygon i moturs riktning.
original på engelska
Problemdeklaration
Tidsgränsen är 4 sekunder.
Du har en tårta. Sett uppifrån är kakan en (strängt) konvex polygon. Du får koordinaterna för dess hörn i int[]sx och y.
Du har fem vänner. Du vill nu skära kakan i sex bitar med lika stor yta (men inte nödvändigtvis lika form). Naturligtvis kan vem som helst göra det i fem snitt - men bara ett riktigt proffs kan göra det på tre!
Hitta tre raka snitt som går genom samma punkt som skar kakan i sex lika stora delar. Returnera {x, y, d1, d2, d3}, där (x, y) är den gemensamma punkten för de tre snitten och d1, d2, d3 är deras riktningar i radianer.
Definition
Klass: CakeForSix
Metod: skär
Parametrar: int[], int[] Returnerar: double[] Metodsignatur: double[] cut(int[] x, int[] y)
(se till att din metod är offentlig)
Anmärkningar
— Den positiva riktningen längs x-axeln är 0 (radianer), den positiva riktningen längs y-axeln är pi/2 (radianer).
— Ett snitt i riktning d är detsamma som ett snitt i riktning pi*k+d för vilket heltal som helst k.
— Du kan returnera alla vägbeskrivningar, de behöver inte vara från [0,pi).
— Gradaren kommer att beräkna ytorna på dina sex kakbitar i dubbel. Svaret kommer att accepteras om den relativa eller absoluta skillnaden mellan dem är mindre än 10^(-4).
— Närmare bestämt, låt X och Y vara de minsta och största av dina sex områden, beräknat av väghyveln. Sedan kommer ditt svar att accepteras om Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Den ursprungliga versionen av problemet använde 1e-7 precision istället för 1e-4. För att lösa detta problem i arkivet sänktes precisionsgränsen på grund av förekomsten av utmaningsfall som med största sannolikhet gör uppgiften olöslig med 1e-7 precision I en idealisk värld skulle begränsningarna inte tillåta sådana fall och fortfarande kräva hög precision, så att det inte är lätt att lösa problemet via någon generell numerisk optimering.)
begränsningar
— x kommer att ha mellan 3 och 50 element, inklusive.
— y kommer att ha samma antal element som x.
— Alla koordinater kommer att vara mellan 0 och 10,000 XNUMX inklusive.
— x och y kommer att beskriva en konvex polygon i moturs ordning.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returnerar:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
En symmetrisk men oregelbunden hexagon. Exempelsvaret motsvarar att skära det på mitten horisontellt och göra två andra nedskärningar i mitten som delar varje bit i tre delar.
1)
{0, 1000, 0}
{0, 0, 1000}
Returnerar:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Rätt triangel. Återigen kan vi börja med en av tre snitt längs symmetriaxeln.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returnerar:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Oregelbunden femhörning.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returer: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
En kvadrat roterad 45 grader.
[]
Endast registrerade användare kan delta i undersökningen. , Snälla du.
Jag löste problemet för
-
på mindre än 10 minuter
-
10-30 minuter
-
30-60 minuter
-
1-2 timmar
-
på mer än 2 timmar
-
andra
42 användare röstade. 47 användare avstod från att rösta.
Källa: will.com