🥇Uppgift med TopCoder Open 2019: skär tårtan i sex delar

Uppgiften från TopCoder Open 2019: skär tårtan i sex delar
I spåren av «Våra vann: TopCoder Open 2019» jag publicerar uppgifter från spåret Algorithm (klassisk sportprogrammering. Inom en och en halv timme måste tre uppgifter lösas i Java, C#, C++ eller Python.)

1. Tårta för sex

Uppgiftsställande

Tidsgräns — 4 sekunder.

Du har en tårta. Om du tittar uppifrån har tårtan formen av (strikt) en konvex polygon. Du får koordinaterna för hörnen i hela tal X och Y.

Du har fem vänner. Du vill dela tårtan i sex delar med lika areal (men inte nödvändigtvis lika mycket form). Självklart kan vem som helst göra detta på fem skärningar, men endast en proffs kan göra det på tre skärningar.

Hitta tre skärningar med raka linjer genom en punkt som delar tårtan i sex delar med lika mycket areal. Skriv ut {x, y, d1, d2, d3}, där (x, y) är den gemensamma punkten för alla tre skärningarna, och d1, d2, d3 är vinklarna för skärningarna i radianer.

DefinitionKlass: CakeForSix
Metod: cut
Parametrar: int[], int[]
Returnerar: double[]
Metodsignatur: double[] cut(int[] x, int[] y)
(se till att din metod är public)

Anteckningar

Det positiva riktningen längs x-axeln är 0 (radianer), det positiva riktningen längs y-axeln är pi/2 (radianer).
En skärning i riktningen d är likvärdig med en skärning i riktningen pi*k+d för varje heltal k.
Du kan returnera valfria riktningar, de behöver inte nödvändigtvis ligga inom [0, pi).
Graderaren kommer att beräkna areorna för dina sex bitar av tårta som doubles. Svaret kommer att accepteras om den relativa eller absoluta skillnaden mellan dem är mindre än 10^(-4).
Mer specifikt, låt X och Y vara de minsta och största av dina sex områden, beräknade av graderaren. Då kommer ditt svar att accepteras om Y <max (X+10^(-4), X*1+10^(-4))).
(I den ursprungliga versionen av uppgiften användes en noggrannhet på 1e-7 istället för 1e-4. För att lösa detta problem sänktes noggrannhetsgränsen i arkivet på grund av förekomsten av fall som sannolikt gör uppgiften olöslig med en noggrannhet på 1e-7. I en ideal värld tillåter begränsningarna inte sådana fall och kräver fortfarande hög noggrannhet, så att åtgärda problemet med någon allmän numerisk optimering är inte enkelt.)

Begränsningar

x innehåller mellan 3 och 50 element inklusive.
y innehåller lika många element som x.
alla koordinater mellan 0 och 10 000 inklusive
x och y definierar en konvex polygon i moturs riktning.

Originalet på engelska

Problemställning

Tidsgränsen är 4 sekunder.

Du har en tårta. Sedd från ovan är tårtan en (strikt) konvex polygon. Du får koordinaterna för dess hörn i int[]-arrayerna x och y.

Du har fem vänner. Du vill nu dela tårtan i sex delar med lika area (men inte nödvändigtvis lika form). Självklart kan vem som helst göra det med fem snitt — men bara en riktig proffs kan göra det med tre!

Hitta tre raka snitt som går genom samma punkt och som delar tårtan i sex lika stora delar. Återvänd {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: cut
Parametrar: int[], int[]
Returnerar: double[]
Metodsignatur: double[] cut(int[] x, int[] y)
(se till att din metod är public)

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 riktning d är detsamma som ett snitt i riktning pi*k+d för varje heltal k.
— Du kan returnera vilka riktningar som helst, de behöver inte vara inom [0,pi).
— Bedömaren kommer att beräkna areorna av dina sex tårtstycken i doubles. Svaret kommer att accepteras om den relativa eller absoluta skillnaden mellan dem är mindre än 10^(-4).
— Mer precis, låt X och Y vara den minsta och den största av dina sex areor, beräknade av bedömaren. Då 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 existensen av utmaningsfall som troligen gör uppgiften olösbar med 1e-7 precision. I en ideal 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, inklusive.
— x och y kommer att beskriva en konvex polygon i moturs riktning.

Exempel

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Återvänder:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Symmetrisk, men inte regelbunden sexhörning. Ett exempel på svaret motsvarar att skära den i två delar horisontellt och göra två andra snitt på mitten som delar varje del i tre delar.

Uppgiften från TopCoder Open 2019: skär tårtan i sex delar

1)

{0, 1000, 0}
{0, 0, 1000}
Återvänder:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Rätvinklig triangel. Återigen kan vi börja med ett av de tre snitten längs symmetriaxeln.

Uppgiften från TopCoder Open 2019: skär tårtan i sex delar

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Återvänder:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Oregelbunden femhörning.

Uppgiften från TopCoder Open 2019: skär tårtan i sex delar

3)