Aufgabe mit TopCoder Open 2019: Kuchen in sechs Teile schneiden

Auf den Spuren „Unsere haben gewonnen: TopCoder Open 2019“ Ich veröffentliche Aufgaben aus dem Track Algorithmus (klassisches Sportprogrammieren. In anderthalb Stunden müssen drei Aufgaben in Java, C#, C++ oder Python gelöst werden.)

1. Kuchen für sechs

Aufgabenstellung

Zeitlimit – 4 Sekunden.

Sie haben einen Kuchen. Wenn man von oben schaut, hat der Kuchen die Form eines (streng) konvexen Vielecks. Ihnen sind die Koordinaten der Eckpunkte in ganzen Zahlen X und Y gegeben.

Sie haben fünf Freunde. Sie möchten den Kuchen in sechs Teile mit gleicher Fläche teilen (aber nicht unbedingt in derselben Form). Natürlich kann das jeder in fünf Schnitten tun, aber nur ein Profi kann das in drei Schnitten schaffen.

Finden Sie drei Schnitte durch einen Punkt, die den Kuchen in sechs gleich große Teile aufteilen. Geben Sie {x, y, d1, d2, d3} aus, wobei (x, y) der gemeinsame Punkt aller drei Schnitte ist und d1, d2, d3 die Richtungswinkel der Schnitte in Radiant sind.

DefinitionKlasse: KuchenFürSechs
Methode: schneiden
Parameter: int[], int[]
Gibt zurück: double[]
Methodensignatur: double[] schneiden(int[] x, int[] y)
(stellen Sie sicher, dass Ihre Methode öffentlich ist)

Anmerkungen

• Die positive Richtung entlang der x-Achse entspricht 0 (Radiant), die positive Richtung entlang der y-Achse entspricht pi/2 (Radiant).
• Ein Schnitt in Richtung d ist ähnlich einem Schnitt in Richtung pi*k+d für jede ganze Zahl k.
• Sie können beliebige Richtungen ausgeben, sie müssen nicht unbedingt im Bereich [0, pi) liegen.
• Der Prüfer berechnet die Flächen Ihrer sechs Stücke Kuchen in Doubles. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen kleiner ist als 10^(-4).
• Genauer gesagt, seien X und Y die kleinsten und größten der sechs von Ihrem Prüfer berechneten Flächen. Dann wird Ihre Antwort akzeptiert, wenn Y < max(X+10^(-4), X*1+10^(-4))).
• (In der ursprünglichen Version der Aufgabe wurde eine Genauigkeit von 1e-7 anstelle von 1e-4 verwendet. Um dieses Problem zu lösen, wurde im Archiv die Genauigkeitsgrenze gesenkt, da es Aufruffälle gab, die die Aufgabe wahrscheinlich unlösbar bei 1e-7 machen. In einer idealen Welt erlauben die Beschränkungen solche Fälle nicht und erfordern immer noch hohe Genauigkeit, sodass es nicht einfach ist, das Problem mit einer allgemeinen numerischen Optimierung zu lösen.)

Einschränkungen

• x enthält von 3 bis 50 Elemente einschließlich.
• y enthält die gleiche Anzahl von Elementen wie x.
• alle Koordinaten liegen zwischen 0 und 10.000 einschließlich
• x und y definieren ein konvexes Vieleck im Gegenuhrzeigersinn.

Original auf Englisch

Problembeschreibung

Zeitlimit beträgt 4 Sekunden.

Du hast einen Kuchen. Von oben betrachtet ist der Kuchen ein (streng) konvexes Polygon. Dir werden die Koordinaten seiner Ecken in den int[]s x und y gegeben.

Du hast fünf Freunde. Du möchtest den Kuchen jetzt in sechs Stücke mit gleicher Fläche (aber nicht unbedingt mit gleicher Form) schneiden. Natürlich kann das jeder in fünf Schnitten tun – aber nur ein echter Profi kann es in drei Schnitten schaffen!

Finde drei gerade Schnitte, die durch denselben Punkt verlaufen und den Kuchen in sechs gleich große Teile schneiden. Gib {x, y, d1, d2, d3} zurück, wobei (x, y) der gemeinsame Punkt der drei Schnitte ist und d1, d2, d3 ihre Richtungen in Radiant sind.

Definition

Klasse: KuchenFürSechs
Methode: schneiden
Parameter: int[], int[]
Gibt zurück: double[]
Methodensignatur: double[] schneiden(int[] x, int[] y)
(stellen Sie sicher, dass Ihre Methode öffentlich ist)

Hinweise
— Die positive Richtung entlang der x-Achse ist 0 (Radiant), die positive Richtung entlang der y-Achse ist pi/2 (Radiant).
— Ein Schnitt in Richtung d ist dasselbe wie ein Schnitt in Richtung pi*k+d für jedes ganze k.
— Du kannst beliebige Richtungen zurückgeben, sie müssen nicht aus [0,pi) stammen.
— Der Bewerter berechnet die Flächen deiner sechs Kuchenstücke in Doubles. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen kleiner als 10^(-4) ist.
— Genauer gesagt, lass X und Y die kleinste und die größte deiner sechs Flächen sein, wie sie vom Bewerter berechnet wurden. Dann wird deine Antwort akzeptiert, wenn Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Die originale Version des Problems verwendete eine Präzision von 1e-7 anstelle von 1e-4. Zur Lösung dieses Problems im Archiv wurde die Präzisionsgrenze reduziert, da es herausfordernde Fälle gibt, die vermutlich die Aufgabe unlösbar mit einer Präzision von 1e-7 machen. In einer idealen Welt würden die Anforderungen solche Fälle nicht zulassen und dennoch hohe Präzision verlangen, sodass es nicht einfach wäre, das Problem durch allgemeine numerische Optimierung zu lösen.)

Einschränkungen
— x wird zwischen 3 und 50 Elemente haben, einschließlich.
— y wird die gleiche Anzahl von Elementen wie x haben.
— Alle Koordinaten liegen zwischen 0 und 10.000, einschließlich.
— x und y beschreiben ein konvexes Polygon in gegen den Uhrzeigersinn.

Beispiele

0)

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Rückgabe:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Symmetrisches, aber nicht regelmäßiges Sechseck. Ein Beispiel für die Antwort entspricht der horizontalen Teilung in zwei Hälften und der Durchführung von zwei weiteren Schnitten in der Mitte, die jedes Stück in drei Teile teilen.

1)

{0, 1000, 0}
{0, 0, 1000}
Rückgabe:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Rechter Winkel Dreieck. Auch hier können wir mit einem der drei Schnitte entlang der Symmetrieachse beginnen.

2)

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

Unregelmäßiges Fünfeck.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Rückgabe: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}

Ein Quadrat, das um 45 Grad gedreht ist.

[Quelle]

Nur registrierte Benutzer können an der Umfrage teilnehmen. Bitte einloggen.

Ich habe die Aufgabe in

• weniger als 10 Minuten gelöst

• 10-30 Minuten

• 30-60 Minuten

• 1-2 Stunden

• mehr als 2 Stunden

• andere

42 Benutzer haben abgestimmt. 47 Benutzer haben sich enthalten.

Quelle: habr.com