En els passos Publico problemes des de la pista de l'algoritme (programació esportiva clàssica. En una hora i mitja cal resoldre tres problemes en Java, C#, C++ o Python.)
1. Pastís per a sis
Declaració de problemes
El límit de temps és de 4 segons.
Tens un pastís. Quan es veu des de dalt, el pastís té la forma d'un polígon (estrictament) convex. Se't donen les coordenades dels vèrtexs en nombres enters X i Y.
Tens cinc amics. Voleu dividir el pastís en sis trossos d'àrea igual (però no necessàriament la mateixa forma). Per descomptat, qualsevol pot fer-ho en cinc talls, però només un professional ho pot fer en tres talls.
Trobeu tres talls de línia recta per un punt que dividiran el pastís en sis parts iguals. Imprimeix {x, y, d1, d2, d3}, on (x, y) és el punt comú dels tres talls, i d1, d2, d3 són els angles de direcció dels talls en radians.
definicióClasse: CakeForSix
Mètode: tallar
Paràmetres: int[], int[] Retorna: double[] Signatura del mètode: double[] cut(int[] x, int[] y)
(assegureu-vos que el vostre mètode sigui públic)
Notes
- La direcció positiva al llarg de l'eix x és 0 (radians), la direcció positiva al llarg de l'eix y és pi/2 (radians).
- Un tall en la direcció d és similar a un tall en la direcció pi*k+d per a qualsevol nombre enter k.
- Podeu sortir qualsevol direcció, no han de ser de [0, pi).
- El qualificador calcularà l'àrea dels vostres sis trossos de pastís en dobles. La resposta s'acceptarà si la diferència relativa o absoluta entre ells és inferior a 10^(-4).
- Més precisament, deixeu que X i Y siguin els més petits i més grans de les vostres sis àrees calculades per l'alumnat. Aleshores la teva resposta serà acceptada si Y
- (La versió original del problema utilitzava una precisió d'1e-7 en lloc d'1e-4. Per resoldre aquest problema a l'arxiu, el límit de precisió es va reduir a causa de la presència de casos de trucada que probablement farien que el problema no es resolgués amb una precisió). de 1e-7. En un món ideal, els límits no permeten aquests casos i encara requereixen una alta precisió, de manera que resoldre el problema amb una optimització numèrica general no és fàcil.)
Restriccions
- x conté de 3 a 50 elements inclosos.
- y conté el mateix nombre d'elements que x.
- totes les coordenades entre 0 i 10 inclosos
- x i y defineixen un polígon convex en sentit contrari a les agulles del rellotge.
Original en anglès
Plantejament del problema
El temps límit és de 4 segons.
Tens un pastís. Vist des de dalt, el pastís és un polígon (estrictament) convex. Se't donen les coordenades dels seus vèrtexs a int[]sx i y.
Tens cinc amics. Ara voleu tallar el pastís en sis trossos d'àrea igual (però no necessàriament de la mateixa forma). Per descomptat, qualsevol pot fer-ho en cinc talls, però només un veritable professional ho pot fer en tres!
Trobeu tres talls en línia recta que passen pel mateix punt que van tallar el pastís en sis parts igualment grans. Torna {x, y, d1, d2, d3}, on (x, y) és el punt comú dels tres talls, i d1, d2, d3 són les seves direccions en radians.
definició
Classe: CakeForSix
Mètode: tallar
Paràmetres: int[], int[] Retorna: double[] Signatura del mètode: double[] cut(int[] x, int[] y)
(assegureu-vos que el vostre mètode sigui públic)
notes
— La direcció positiva al llarg de l'eix x és 0 (radians), la direcció positiva al llarg de l'eix y és pi/2 (radians).
— Un tall en la direcció d és el mateix que un tall en la direcció pi*k+d per a qualsevol nombre enter k.
— Podeu tornar qualsevol indicació, no cal que siguin de [0,pi).
— L'alumnat calcularà les àrees de les vostres sis peces de pastís en dobles. La resposta s'acceptarà si la diferència relativa o absoluta entre ells és inferior a 10^(-4).
— Més precisament, deixeu que X i Y siguin els més petits i més grans de les vostres sis àrees, tal com ha calculat l'alumnat. Aleshores, la teva resposta serà acceptada si Y < max( X + 10^(-4), X * (1+10^(-4))).
— (La versió original del problema utilitzava la precisió 1e-7 en lloc de l'1e-4. Per resoldre aquest problema a l'arxiu, el límit de precisió es va reduir a causa de l'existència de casos de desafiament que probablement fan que la tasca no es resolgui amb precisió 1e-7 En un món ideal, les restriccions no permetrien aquests casos i encara requereixen una alta precisió, de manera que no és fàcil resoldre el problema mitjançant una optimització numèrica general.)
Restriccions
— x tindrà entre 3 i 50 elements, ambdós inclosos.
— y tindrà el mateix nombre d'elements que x.
— Totes les coordenades seran entre 0 i 10,000, ambdós inclosos.
— x i y descriuen un polígon convex en ordre contrari a les agulles del rellotge.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Retorna:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Un hexàgon simètric però irregular. La resposta d'exemple correspon a tallar-lo per la meitat horitzontalment i fer altres dos talls pel centre que divideixen cada peça en tres peces.
1)
{0, 1000, 0}
{0, 0, 1000}
Retorna:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Triangle rectangle. De nou, podem començar amb un dels tres talls al llarg de l'eix de simetria.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Retorna:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pentàgon irregular.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Devolucions: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Un quadrat gira 45 graus.
[]
Només els usuaris registrats poden participar en l'enquesta. si us plau.
Vaig resoldre el problema per
-
en menys de 10 minuts
-
Minuts 10 30-
-
Minuts 30 60-
-
1 2-hora
-
en més de 2 hores
-
un altre
Han votat 42 usuaris. 47 usuaris es van abstenir.
Font: www.habr.com