Siguiendo las huellas publico tareas de la pista Algoritmo (programación competitiva clásica. Tienes que resolver tres problemas en Java, C#, C++ o Python en una hora y media.)
1. Pastel para seis
Planteamiento del problema
Límite de tiempo — 4 segundos.
Tienes un pastel. Si lo miras desde arriba, el pastel tiene la forma de un polígono convexo (estricto). Se te dan las coordenadas de los vértices en enteros X e Y.
Tienes cinco amigos. Quieres dividir el pastel en seis partes de igual área (pero no necesariamente de la misma forma). Por supuesto, cualquiera podría hacerlo con cinco cortes, pero solo un profesional puede hacerlo con tres cortes.
Encuentra tres cortes en línea a través de un punto que dividan el pastel en seis partes de igual área. Devuelve {x, y, d1, d2, d3}, donde (x, y) es el punto común de los tres cortes y d1, d2, d3 son los ángulos de dirección de los cortes en radianes.
DefiniciónClase: CakeForSix
Método: cut
Parámetros: int[], int[]
Devuelve: double[]
Firma del método: double[] cut(int[] x, int[] y)
(asegúrate de que tu método sea público)
Notas
- La dirección positiva a lo largo del eje x es 0 (radianes), la dirección positiva a lo largo del eje y es pi/2 (radianes).
- Un corte en la dirección d es similar a un corte en la dirección pi*k+d para cualquier número entero k.
- Puedes devolver cualquier dirección, no necesariamente tienen que estar en [0, pi).
- El calificador calculará las áreas de tus seis piezas de pastel en doubles. La respuesta será aceptada si la diferencia relativa o absoluta entre ellas es menor que 10^(-4).
- Más precisamente, sean X e Y las áreas más pequeñas y más grandes de tus seis áreas calculadas por el calificador. Entonces tu respuesta será aceptada si Y < max(X+10^(-4), X*1+10^(-4)).
- (En la versión original de la tarea se usaba una precisión de 1e-7 en lugar de 1e-4. Para resolver este problema, en el archivo se redujo el límite de precisión debido a la existencia de casos de llamadas que probablemente hacen la tarea irresoluble con una precisión de 1e-7. En un mundo ideal, las restricciones no deberían permitir tales casos y aún requerirían alta precisión, por lo que resolver el problema mediante alguna optimización numérica general no es sencillo.)
Limitaciones
- x contiene entre 3 y 50 elementos inclusive.
- y contiene la misma cantidad de elementos que x.
- todas las coordenadas entre 0 y 10,000 inclusive
- x e y definen un polígono convexo en dirección antihoraria.
Original en inglés
Declaración del problema
El límite de tiempo es de 4 segundos.
Tienes un pastel. Visto desde arriba, el pastel es un polígono (estrictamente) convexo. Se te dan las coordenadas de sus vértices en los int[]s x e y.
Tienes cinco amigos. Ahora quieres cortar el pastel en seis piezas de área igual (pero no necesariamente de la misma forma). Por supuesto, cualquiera puede hacerlo en cinco cortes, ¡pero solo un verdadero profesional puede hacerlo en tres!
Encuentra tres cortes en línea recta que pasen por el mismo punto y que dividan el pastel en seis partes de igual tamaño. Devuelve {x, y, d1, d2, d3}, donde (x, y) es el punto común de los tres cortes, y d1, d2, d3 son sus direcciones en radianes.
Definición
Clase: CakeForSix
Método: cut
Parámetros: int[], int[]
Devuelve: double[]
Firma del método: double[] cut(int[] x, int[] y)
(asegúrate de que tu método sea público)
Notas
— La dirección positiva a lo largo del eje x es 0 (radianes), la dirección positiva a lo largo del eje y es pi/2 (radianes).
— Un corte en dirección d es lo mismo que un corte en dirección pi*k+d para cualquier entero k.
— Puedes devolver cualquier dirección, no tienen que estar en [0,pi).
— El evaluador calculará las áreas de tus seis piezas de pastel en números dobles. La respuesta será aceptada si la diferencia relativa o absoluta entre ellas es menor que 10^(-4).
— Más precisamente, sea X e Y el menor y el mayor de tus seis áreas, según lo calculado por el evaluador. Entonces, tu respuesta será aceptada si Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (La versión original del problema utilizó una precisión de 1e-7 en lugar de 1e-4. Para resolver este problema en el archivo, se redujo el límite de precisión debido a la existencia de casos desafiantes que probablemente hacen que la tarea sea irresoluble con precisión de 1e-7. En un mundo ideal, las restricciones no permitirían tales casos y aún requerirían alta precisión, de modo que no sea fácil resolver el problema a través de alguna optimización numérica general.)
Restricciones
— x tendrá entre 3 y 50 elementos, inclusivo.
— y tendrá el mismo número de elementos que x.
— Todas las coordenadas estarán entre 0 y 10,000, inclusivo.
— x e y describirán un polígono convexo en orden contra reloj.
Ejemplos
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Devuelve:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Un hexágono simétrico, pero no regular. Un ejemplo de respuesta corresponde a cortarlo por la mitad horizontalmente y realizar otros dos cortes en el centro que dividen cada parte en tres.
1)
{0, 1000, 0}
{0, 0, 1000}
Devuelve:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Un triángulo rectángulo. Nuevamente, podemos comenzar con uno de los tres cortes a lo largo del eje de simetría.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Devuelve:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Un pentágono irregular.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Devuelve: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Un cuadrado girado 45 grados.
[]
Solo los usuarios registrados pueden participar en la encuesta. , por favor.
Resolví el problema en
menos de 10 minutos
10-30 minutos
30-60 minutos
1-2 horas
más de 2 horas
otro
42 usuarios votaron. 47 usuarios se abstuvieron.
Fuente: habr.com
