In der Folge Ich veröffentliche Probleme aus dem Algorithmus-Track (Klassische Sportprogrammierung. In eineinhalb Stunden müssen Sie drei Probleme in Java, C#, C++ oder Python lösen.)
1. Kuchen für sechs
Formulierung des Problems
Das Zeitlimit beträgt 4 Sekunden.
Du hast einen Kuchen. Von oben betrachtet hat der Kuchen die Form eines (streng) konvexen Vielecks. Sie erhalten die Koordinaten der Eckpunkte in X- und Y-Ganzzahlen.
Du hast fünf Freunde. Sie möchten den Kuchen in sechs gleich große Stücke teilen (aber nicht unbedingt die gleiche Form). Natürlich kann es jeder in fünf Schnitten machen, aber nur ein Profi schafft es in drei Schnitten.
Finden Sie drei Schnitte in geraden Linien durch einen Punkt, die den Kuchen in sechs gleiche Teile teilen. Drucken Sie {x, y, d1, d2, d3}, wobei (x, y) der gemeinsame Punkt aller drei Schnitte ist und d1, d2, d3 die Richtungswinkel der Schnitte im Bogenmaß sind.
DefinitionKlasse: CakeForSix
Methode: Schnitt
Parameter: int[], int[] Rückgabewerte: double[] Methodensignatur: double[] cut(int[] x, int[] y)
(Stellen Sie sicher, dass Ihre Methode öffentlich ist)
Aufzeichnungen
- Die positive Richtung entlang der x-Achse ist 0 (Bogenmaß), die positive Richtung entlang der y-Achse ist pi/2 (Bogenmaß).
- Ein Schnitt in d-Richtung ähnelt einem Schnitt in pi*k+d-Richtung für jede ganze Zahl k.
- Sie können beliebige Richtungen ausgeben, diese müssen nicht von [0, pi) ausgehen.
- Der Bewerter berechnet die Fläche Ihrer sechs Kuchenstücke im Doppel. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen weniger als 10^(-4) beträgt.
- Genauer gesagt seien X und Y die kleinsten und größten Ihrer sechs vom Grader berechneten Flächen. Dann wird Ihre Antwort akzeptiert, wenn Y
- (In der ursprünglichen Version des Problems wurde eine Genauigkeit von 1e-7 anstelle von 1e-4 verwendet. Um dieses Problem im Archiv zu lösen, wurde die Genauigkeitsgrenze aufgrund des Vorhandenseins von Aufruffällen gesenkt, die das Problem wahrscheinlich mit einer Genauigkeit unlösbar machen würden von 1e-7. In einer idealen Welt erlauben die Grenzwerte solche Fälle nicht und erfordern dennoch eine hohe Präzision, sodass die Lösung des Problems mit einer allgemeinen numerischen Optimierung nicht einfach ist.)
Einschränkungen
- x enthält 3 bis einschließlich 50 Elemente.
- y enthält die gleiche Anzahl an Elementen wie x.
- alle Koordinaten zwischen 0 und 10 inklusive
- x und y definieren ein konvexes Polygon im Gegenuhrzeigersinn.
Original in Englisch
Problem Statement
Das Zeitlimit beträgt 4 Sekunden.
Du hast einen Kuchen. Von oben gesehen ist der Kuchen ein (streng) konvexes Polygon. Sie erhalten die Koordinaten seiner Eckpunkte in int[]sx und y.
Du hast fünf Freunde. Sie möchten den Kuchen nun in sechs gleich große (aber nicht unbedingt gleich geformte) Stücke schneiden. Natürlich kann das jeder in fünf Schnitten machen – aber nur ein echter Profi schafft es in drei!
Finden Sie drei geradlinige Schnitte, die durch denselben Punkt verlaufen und den Kuchen in sechs gleich große Teile schneiden. Gibt {x, y, d1, d2, d3} zurück, wobei (x, y) der gemeinsame Punkt der drei Schnitte ist und d1, d2, d3 ihre Richtungen im Bogenmaß sind.
Definition
Klasse: CakeForSix
Methode: Schnitt
Parameter: int[], int[] Rückgabewerte: double[] Methodensignatur: double[] cut(int[] x, int[] y)
(Stellen Sie sicher, dass Ihre Methode öffentlich ist)
Notizen
— Die positive Richtung entlang der x-Achse ist 0 (Bogenmaß), die positive Richtung entlang der y-Achse ist pi/2 (Bogenmaß).
— Ein Schnitt in Richtung d ist dasselbe wie ein Schnitt in Richtung pi*k+d für jede ganze Zahl k.
— Sie können beliebige Richtungen zurückgeben, diese müssen nicht von [0,pi) ausgehen.
— Der Grader berechnet die Flächen Ihrer sechs Kuchenstücke im Doppel. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen weniger als 10^(-4) beträgt.
– Genauer gesagt seien X und Y die kleinsten und größten Ihrer sechs Flächen, wie sie vom Grader berechnet wurden. Dann wird Ihre Antwort akzeptiert, wenn Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (In der ursprünglichen Version des Problems wurde eine Genauigkeit von 1e-7 anstelle von 1e-4 verwendet. Um dieses Problem im Archiv zu lösen, wurde die Genauigkeitsgrenze gesenkt, da es Herausforderungsfälle gibt, die die Aufgabe höchstwahrscheinlich mit einer Genauigkeit von 1e-7 unlösbar machen In einer idealen Welt würden die Einschränkungen solche Fälle nicht zulassen und dennoch eine hohe Präzision erfordern, so dass es nicht einfach ist, das Problem durch eine allgemeine numerische Optimierung zu lösen.)
Einschränkungen
– x wird zwischen 3 und 50 Elementen haben.
— y wird die gleiche Anzahl von Elementen haben wie x.
— Alle Koordinaten liegen zwischen 0 und 10,000 (einschließlich).
— x und y beschreiben ein konvexes Polygon in der Reihenfolge gegen den Uhrzeigersinn.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Rücksendung:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Ein symmetrisches, aber unregelmäßiges Sechseck. Die Beispielantwort besteht darin, es horizontal in zwei Hälften zu schneiden und zwei weitere Schnitte in der Mitte vorzunehmen, die jedes Stück in drei Teile teilen.
1)
{0, 1000, 0}
{0, 0, 1000}
Rücksendung:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Rechtwinkliges Dreieck. Auch hier können wir mit einem von drei Schnitten entlang der Symmetrieachse beginnen.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Rücksendung:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Unregelmäßiges Fünfeck.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Rückgabewerte: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Ein um 45 Grad gedrehtes Quadrat.
[]
An der Umfrage können nur registrierte Benutzer teilnehmen. bitte.
Ich habe das Problem gelöst
-
in weniger als 10 Minuten
-
10-30 Minuten
-
30-60 Minuten
-
1-2 Stunden
-
in mehr als 2 Stunden
-
andere
42 Benutzer haben abgestimmt. 47 Benutzer enthielten sich der Stimme.
Source: habr.com