Auf den Spuren Ich veröffentliche Aufgaben aus dem Bereich Algorithmus (klassisches sportliches Programmieren. In anderthalb Stunden müssen drei Aufgaben in Java, C#, C++ oder Python gelöst werden.)
1. Kuchen für sechs
Problemstellung
Zeitlimit – 4 Sekunden.
Sie haben einen Kuchen. Wenn man von oben schaut, hat der Kuchen die Form eines (streng) konvexen Polygons. Ihnen sind die Koordinaten der Ecken in ganzen Zahlen X und Y gegeben.
Sie haben fünf Freunde. Sie möchten den Kuchen in sechs Teile mit gleich großer Fläche (aber nicht unbedingt in gleicher Form) aufteilen. Natürlich kann das jeder in fünf Schnitten tun, aber nur ein Profi kann das in drei Schnitten erreichen.
Finden Sie drei Schnittlinien durch einen Punkt, die den Kuchen in sechs gleich große Flächen teilen. Geben Sie {x, y, d1, d2, d3} aus, wobei (x, y) der gemeinsame Punkt aller drei Schnitte ist und d1, d2, d3 die Richtung der Schnitte in Radiant sind.
DefinitionKlasse: CakeForSix
Methode: cut
Parameter: int[], int[]
Rückgabe: double[]
Methodensignatur: double[] cut(int[] x, int[] y)
(Stellen Sie sicher, dass Ihre Methode öffentlich ist)
Hinweise
- Die positive Richtung entlang der x-Achse entspricht 0 (Radiant), die positive Richtung entlang der y-Achse entspricht pi/2 (Radiant).
- Der Schnitt in Richtung d ist dem Schnitt in der Richtung pi*k+d für jede ganze Zahl k ähnlich.
- Sie können beliebige Richtungen angeben, diese müssen nicht unbedingt im Bereich [0, pi) liegen.
- Der Grader berechnet die Flächen Ihrer sechs Stücke Kuchen in doubles. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen kleiner als 10^(-4) ist.
- Genauer gesagt, seien X und Y die kleinste und die größte Ihrer sechs Flächen, die der Grader berechnet hat. 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 aufgrund von Aufruffällen herabgesetzt, die möglicherweise die Aufgabe unlösbar bei einer Genauigkeit von 1e-7 machen. In einer perfekten Welt lassen die Einschränkungen solche Fälle nicht zu und erfordern immer noch eine 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 genauso viele Elemente wie x.
- alle Koordinaten liegen zwischen 0 und 10.000 einschließlich.
- x und y definieren ein konvexes Polygon gegen den Uhrzeigersinn.
Ursprünglich in Englisch
Problemstellung
Die Zeitbegrenzung beträgt 4 Sekunden.
Sie haben eine Torte. Von oben betrachtet ist die Torte ein (streng) konvexes Polygon. Ihnen werden die Koordinaten ihrer Eckpunkte in den int[]-Arrays x und y gegeben.
Sie haben fünf Freunde. Nun möchten Sie die Torte in sechs Stücke mit gleichem Gebiet (aber nicht unbedingt gleicher Form) schneiden. Natürlich kann das jeder in fünf Schnitten tun – aber nur ein wahrer Profi kann es in dreien schaffen!
Finden Sie drei gerade Schnitte, die durch denselben Punkt verlaufen und die Torte in sechs gleich große Teile schneiden. Geben Sie {x, y, d1, d2, d3} zurück, wobei (x, y) der gemeinsame Punkt der drei Schnitte ist und d1, d2, d3 deren Richtungen in Bogenmaß.
Definition
Klasse: CakeForSix
Methode: cut
Parameter: int[], int[]
Rückgabe: double[]
Methodensignatur: double[] cut(int[] x, int[] y)
(Stellen Sie sicher, dass Ihre Methode öffentlich ist)
Hinweise
— 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 jedes ganze k.
— Sie können beliebige Richtungen zurückgeben, sie müssen nicht aus [0,pi) stammen.
— Der Bewerter berechnet die Flächen Ihrer sechs Tortenstücke in Doubles. Die Antwort wird akzeptiert, wenn die relative oder absolute Differenz zwischen ihnen kleiner als 10^(-4) ist.
— Genauer gesagt, seien X und Y die kleinste und die größte Ihrer sechs Flächen, wie vom Bewerter berechnet. Ihre Antwort wird akzeptiert, wenn Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Die ursprüngliche Version des Problems verwendete eine Präzision von 1e-7 anstelle von 1e-4. Für die Lösung dieses Problems im Archiv wurde die Präzisionsgrenze aufgrund der Existenz von Herausforderungsfällen, die das Problem wahrscheinlich mit einer Präzision von 1e-7 unlösbar machen, gesenkt. In einer idealen Welt würden die Einschränkungen solche Fälle nicht zulassen und dennoch eine hohe Präzision erfordern, sodass es nicht einfach wäre, das Problem durch allgemeine numerische Optimierung zu lösen.)
Einschränkungen
— x wird zwischen 3 und 50 Elemente enthalten, 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 im Gegenuhrzeigersinn.
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 }
Symmetrischer, aber nicht regelmäßiger Sechseck. Ein Beispiel für die Antwort entspricht dem horizontalen Teilen in zwei Hälften und dem Durchführen von zwei weiteren Schnitten in der Mitte, die jedes Teil in drei Teile unterteilen.
1)
{0, 1000, 0}
{0, 0, 1000}
Rückgabe:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Rechtwinkliges 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 }
Quadrat, um 45 Grad gedreht.
[]
Nur registrierte Benutzer können an der Umfrage teilnehmen. Sind Sie an Contour interessiert?
Ich habe die Aufgabe in
weniger als 10 Minuten gelöst.
10-30 Minuten
30-60 Minuten
1-2 Stunden
mehr als 2 Stunden
anderes
42 Benutzer haben abgestimmt. 47 Benutzer haben sich enthalten.
Quelle: habr.com
