🥇 TopCoder Open 2019 uitdaging: de taart in zes stukken snijden

Opdracht met TopCoder Open 2019: verdeel de taart in zes stukken
Op zoek naar «Onze winnaars: TopCoder Open 2019» Publiceer taken van de Algorithm-track (klassiek wedstrijdprogrammeren. Je moet in anderhalf uur drie taken oplossen in Java, C#, C++ of Python.)

1. Taart voor zes

Taakstelling

De tijdslimiet is 4 seconden.

Je hebt een taart. Van bovenaf gezien heeft de taart de vorm van een (strikt) convexe veelhoek. Je krijgt de coördinaten van de hoekpunten in gehele getallen X en Y.

Je hebt vijf vrienden. Je wilt de taart in zes delen van gelijke oppervlakte delen (maar niet per se dezelfde vorm). Iedereen kan dat natuurlijk met vijf sneden doen, maar alleen een professional kan dat met drie sneden.

Vind drie sneden met rechte lijnen die door één punt gaan en de taart in zes gelijkwaardige oppervlakte delen verdelen. Geef {x, y, d1, d2, d3} weer, waarbij (x, y) het gemeenschappelijke punt van alle drie de sneden is, en d1, d2, d3 de hoeken van de sneden in radialen zijn.

DefinitieKlasse: CakeForSix
Methode: cut
Parameters: int[], int[]
Retourneert: double[]
Methodehandtekening: double[] cut(int[] x, int[] y)
(zorg ervoor dat je methode openbaar is)

Opmerkingen

De positieve richting langs de x-as is gelijk aan 0 (radialen), de positieve richting langs de y-as is gelijk aan pi/2 (radialen).
Een snede in de richting d is vergelijkbaar met een snede in de richting pi*k+d voor elk geheel getal k.
Je mag elke richting opgeven, ze hoeven niet per se van [0, pi) te zijn.
De grader berekent de oppervlaktes van je zes taartstukken in doubles. Het antwoord wordt geaccepteerd als het relatieve of absolute verschil tussen hen minder is dan 10^(-4).
Specifieker, laat X en Y de kleinste en grootste van je zes gebieden zijn, berekend door de grader. Je antwoord wordt geaccepteerd als Y < max (X + 10^(-4), X * 1 + 10^(-4)).
(In de oorspronkelijke versie van de taak werd een nauwkeurigheid van 1e-7 gebruikt in plaats van 1e-4. Dit probleem is verlaagd vanwege situaties die de taak waarschijnlijk onoplosbaar maken met een nauwkeurigheid van 1e-7. In een ideale wereld zouden beperkingen dergelijke gevallen niet toestaan en toch een hoge nauwkeurigheid vereisen, dus het oplossen van het probleem met enige algemene numerieke optimalisatie is niet eenvoudig.)

Beperkingen

x bevat van 3 tot 50 elementen inclusief.
y bevat net zoveel elementen als x.
alle coördinaten liggen tussen 0 en 10.000 inclusief
x en y definiëren een convexe veelhoek tegen de klok in.

Origineel in het Engels

Probleemstelling

De tijdslimiet is 4 seconden.

Je hebt een taart. Van bovenaf gezien is de taart een (strikt) convexe veelhoek. Je krijgt de coördinaten van zijn hoekpunten in de int[]s x en y.

Je hebt vijf vrienden. Je wilt de taart nu in zes stukken van gelijke oppervlakte snijden (maar niet noodzakelijk van gelijke vorm). Natuurlijk kan iedereen dat in vijf snedes doen — maar alleen een echte professional kan het in drie doen!

Vind drie rechte sneden die door hetzelfde punt gaan en de taart in zes gelijkwaardige delen snijden. Geef {x, y, d1, d2, d3} terug, waar (x, y) het gemeenschappelijke punt is van de drie sneden, en d1, d2, d3 hun richtingen in radialen zijn.

Definitie

Klasse: CakeForSix
Methode: cut
Parameters: int[], int[]
Retourneert: double[]
Methodehandtekening: double[] cut(int[] x, int[] y)
(zorg ervoor dat je methode openbaar is)

Opmerkingen
— De positieve richting langs de x-as is 0 (radialen), de positieve richting langs de y-as is pi/2 (radialen).
— Een snede in richting d is hetzelfde als een snede in richting pi*k+d voor elke integer k.
— Je mag elke richting teruggeven, ze hoeven niet uit [0,pi) te komen.
— De grader zal de oppervlakten van je zes taartstukken in doubles berekenen. Het antwoord wordt geaccepteerd als het relatieve of absolute verschil tussen hen kleiner is dan 10^(-4).
— Meer precies, laat X en Y de kleinste en de grootste van je zes oppervlakten zijn, zoals berekend door de grader. Dan wordt je antwoord geaccepteerd als Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (De oorspronkelijke versie van het probleem gebruikte 1e-7 precisie in plaats van 1e-4. Voor het oplossen van dit probleem in het archief is de precisielimiet verlaagd vanwege de aanwezigheid van uitdagende gevallen die hoogstwaarschijnlijk de taak onoplosbaar maken met 1e-7 precisie. In een ideale wereld zouden de beperkingen dergelijke gevallen niet toestaan en toch een hoge precisie vereisen, zodat het niet gemakkelijk is om het probleem op te lossen via een algemene numerieke optimalisatie.)

Beperkingen
— x zal tussen de 3 en 50 elementen hebben, inclusief.
— y zal hetzelfde aantal elementen hebben als x.
— Alle coördinaten zullen tussen 0 en 10.000 liggen, inclusief.
— x en y beschrijven een convexe veelhoek in tegenwijzerzin.

Voorbeelden

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Retourneert:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Symmetrische, maar geen regelmatige zeshoek. Voorbeeldantwoord komt overeen met het doormidden snijden van de taart langs de horizontale lijn en het maken van twee andere sneden door het midden, die elk stuk in drie delen splitsen.

Opdracht met TopCoder Open 2019: verdeel de taart in zes stukken

1)

{0, 1000, 0}
{0, 0, 1000}
Retourneert:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Rechthoekige driehoek. Nogmaals, we kunnen beginnen met een van de drie sneden langs de symmetrieas.

Opdracht met TopCoder Open 2019: verdeel de taart in zes stukken

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Retourneert:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Onregelmatige vijfhoek.

Opdracht met TopCoder Open 2019: verdeel de taart in zes stukken

3)