Tâche de TopCoder Open 2019 : couper le gâteau en six parts

Sur la trace «Nos vainqueurs : TopCoder Open 2019» je publie des problèmes du parcours Algorithm (programmation compétitive classique. Vous devez résoudre trois problèmes en une heure et demie en Java, C#, C++ ou Python.)

1. Gâteau pour six

Définition du problème

Limite de temps — 4 secondes.

Vous avez un gâteau. Si vous regardez par le dessus, le gâteau a la forme d'un polygone (strictement) convexe. On vous donne les coordonnées des sommets sous forme d'entiers X et Y.

Vous avez cinq amis. Vous souhaitez partager le gâteau en six parts égales (mais pas nécessairement de la même forme). Bien sûr, n'importe qui peut le faire en cinq coupes, mais seul un pro peut le faire en trois coupes.

Trouvez trois coupes en lignes passant par un point commun qui partageront le gâteau en six parts égales en surface. Affichez {x, y, d1, d2, d3}, où (x, y) est le point commun de toutes les trois coupes, et d1, d2, d3 sont les angles de direction des coupes en radians.

DéfinitionClasse : CakeForSix
Méthode : cut
Paramètres : int[], int[]
Retourne : double[]
Signature de la méthode : double[] cut(int[] x, int[] y)
(assurez-vous que votre méthode est publique)

Notes

• La direction positive le long de l'axe des x est égale à 0 (radian), la direction positive le long de l'axe des y est égale à pi/2 (radian).
• Une coupe dans la direction d est semblable à une coupe dans la direction pi*k+d pour tout entier k.
• Vous pouvez afficher n'importe quelle direction, elles ne doivent pas nécessairement être dans [0, pi).
• Le grader calculera les surfaces de vos six morceaux de gâteau en doubles. La réponse sera acceptée si la différence relative ou absolue entre elles est inférieure à 10^(-4).
• Plus précisément, soit X et Y les plus petites et les plus grandes de vos six surfaces calculées par le grader. Votre réponse sera acceptée si Y < max(X+10^(-4), X*1+10^(-4))).
• (Dans la version originale du problème, une précision de 1e-7 était utilisée au lieu de 1e-4. Pour résoudre ce problème, la limite de précision a été abaissée dans les archives à cause de cas d'appels qui rendent probablement le problème insoluble avec une précision de 1e-7. Dans un monde idéal, les contraintes ne permettraient pas de tels cas et exigeraient encore une haute précision, donc résoudre le problème par une optimisation numérique commune n'est pas simple.)

Restrictions

• x contient entre 3 et 50 éléments inclus.
• y contient le même nombre d'éléments que x.
• toutes les coordonnées entre 0 et 10 000 inclus.
• x et y définissent un polygone convexe dans le sens antihoraire.

Original en anglais

Énoncé du problème

La limite de temps est de 4 secondes.

Vous avez un gâteau. Vu d'en haut, le gâteau est un polygone (strictement) convexe. Vous avez les coordonnées de ses sommets dans les tableaux int[] x et y.

Vous avez cinq amis. Vous souhaitez maintenant couper le gâteau en six morceaux de même aire (mais pas nécessairement de même forme). Bien sûr, quelqu'un peut le faire en cinq coupes — mais seul un vrai pro peut le faire en trois !

Trouvez trois coupes rectilignes passant par le même point qui divisent le gâteau en six parts de même taille. Retournez {x, y, d1, d2, d3}, où (x, y) est le point commun des trois coupes, et d1, d2, d3 sont leurs directions en radians.

Définition

Classe : CakeForSix
Méthode : cut
Paramètres : int[], int[]
Retourne : double[]
Signature de la méthode : double[] cut(int[] x, int[] y)
(assurez-vous que votre méthode est publique)

Remarques
— La direction positive le long de l'axe des x est 0 (radians), la direction positive le long de l'axe des y est pi/2 (radians).
— Une coupe dans la direction d est équivalente à une coupe dans la direction pi*k+d pour tout entier k.
— Vous pouvez retourner n'importe quelle direction, elles n'ont pas besoin d'être dans [0,pi).
— Le correcteur calculera les aires de vos six morceaux de gâteau en nombres décimaux. La réponse sera acceptée si la différence relative ou absolue entre elles est inférieure à 10^(-4).
— Plus précisément, soit X et Y les plus petites et plus grandes de vos six aires, comme calculé par le correcteur. Votre réponse sera acceptée si Y < max(X + 10^(-4), X * (1+10^(-4))).
— (La version originale du problème utilisait une précision de 1e-7 au lieu de 1e-4. Pour résoudre ce problème dans l'archive, la limite de précision a été abaissée en raison de l'existence de cas difficiles qui rendent probablement la tâche insolvable avec une précision de 1e-7. Dans un monde idéal, les contraintes ne permettraient pas de tels cas tout en nécessitant une haute précision, de sorte qu'il n'est pas facile de résoudre le problème par une optimisation numérique générale.)

Contraintes
— x contiendra entre 3 et 50 éléments inclus.
— y aura le même nombre d'éléments que x.
— Toutes les coordonnées seront comprises entre 0 et 10 000 inclus.
— x et y décriront un polygone convexe dans le sens antihoraire.

Exemples

0)

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

Un hexagone symétrique mais irrégulier. Un exemple de réponse correspond à la coupe en deux parties horizontalement et à la réalisation de deux autres coupes au centre, qui divisent chaque section en trois parties.

1)

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

Un triangle rectangle. Encore une fois, nous pouvons commencer par l'une des trois coupes le long de l'axe de symétrie.

2)

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

Un pentagone irrégulier.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Retours : {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

Un carré, tourné de 45 degrés.

[Source]

Seuls les utilisateurs enregistrés peuvent participer au sondage. Connectez-vous, s'il vous plaît.

J'ai résolu le problème en

• moins de 10 minutes

• 10-30 minutes

• 30-60 minutes

• 1-2 heures

• plus de 2 heures

• autre

42 utilisateurs ont voté. 47 utilisateurs se sont abstenus.

Source : habr.com