En la estela Publico problemas de la pista de Algoritmo. (Programación deportiva clásica. En una hora y media necesitas resolver tres problemas en Java, C#, C++ o Python.)
1. Pastel para seis
Formulación del problema
El límite de tiempo es de 4 segundos.
Tienes un pastel. Visto desde arriba, el pastel tiene la forma de un polígono (estrictamente) convexo. Se te dan las coordenadas de los vértices en números 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 puede hacerlo en cinco cortes, pero sólo un profesional puede hacerlo en tres cortes.
Encuentra tres cortes en línea recta a través de un punto que dividirán el pastel en seis partes iguales. Imprima {x, y, d1, d2, d3}, donde (x, y) es el punto común de los tres cortes y d1, d2, d3 son los ángulos directores de los cortes en radianes.
DefiniciónClase: CakeForSix
Método: cortar
Parámetros: int[], int[] Devuelve: double[] Firma del método: double[] cut(int[] x, int[] y)
(asegúrese de que su 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.
- Puede generar cualquier dirección, no es necesario que sean desde [0, pi).
- El clasificador calculará el área de tus seis trozos de pastel por duplicados. Se aceptará la respuesta si la diferencia relativa o absoluta entre ellos es menor que 10^(-4).
- Más precisamente, sean X e Y las más pequeñas y las más grandes de las seis áreas calculadas por el clasificador. Entonces su respuesta será aceptada si Y
- (La versión original del problema usaba una precisión de 1e-7 en lugar de 1e-4. Para resolver este problema en el archivo, el límite de precisión se redujo debido a la presencia de casos de llamadas que probablemente harían que el problema no pudiera resolverse con una precisión de 1e-7. En un mundo ideal, los límites no permiten tales casos y aún requieren alta precisión, por lo que resolver el problema con alguna optimización numérica general no es fácil).
restricciones
- x contiene de 3 a 50 elementos inclusive.
- y contiene el mismo número de elementos que x.
- todas las coordenadas entre 0 y 10 inclusive
- x e y definen un polígono convexo en sentido antihorario.
Original en ingles
Planteamiento 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 le dan las coordenadas de sus vértices en int[]sx e y.
Tienes cinco amigos. Ahora desea cortar el pastel en seis trozos de igual área (pero no necesariamente de igual forma). Por supuesto, cualquiera puede hacerlo en cinco cortes, ¡pero sólo un verdadero profesional puede hacerlo en tres!
Encuentra tres cortes en línea recta que pasen por el mismo punto que corta el pastel en seis partes igualmente grandes. 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: cortar
Parámetros: int[], int[] Devuelve: double[] Firma del método: double[] cut(int[] x, int[] y)
(asegúrese de que su 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 lo mismo que un corte en la dirección pi*k+d para cualquier número entero k.
— Puedes devolver cualquier dirección, no es necesario que sean desde [0,pi).
— El clasificador calculará las áreas de los seis trozos de pastel en dobles. Se aceptará la respuesta si la diferencia relativa o absoluta entre ellos es menor que 10^(-4).
— Más precisamente, sean X e Y la más pequeña y la más grande de sus seis áreas, calculadas por el evaluador. Entonces, su respuesta será aceptada si Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (La versión original del problema usaba precisión 1e-7 en lugar de 1e-4. Para resolver este problema en el archivo, el límite de precisión se redujo debido a la existencia de casos de desafío que probablemente hacen que la tarea no se pueda resolver con precisión 1e-7 En un mundo ideal, las restricciones no permitirían tales casos y aún requerirían alta precisión, por lo que no es fácil resolver el problema mediante alguna optimización numérica general).
Limitaciones
— x tendrá entre 3 y 50 elementos, inclusive.
— y tendrá el mismo número de elementos que x.
— Todas las coordenadas estarán entre 0 y 10,000, inclusive.
- xey describirán un polígono convexo en orden antihorario.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Devoluciones:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}
Un hexágono simétrico pero irregular. La respuesta del ejemplo corresponde a cortarlo por la mitad horizontalmente y hacer otros dos cortes por el centro que dividen cada trozo en tres trozos.
1)
{0, 1000, 0}
{0, 0, 1000}
Devoluciones:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753}
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}
Devoluciones:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475}
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 gira 45 grados.
[]
Solo los usuarios registrados pueden participar en la encuesta. por favor
Resolví el problema por
-
en menos de 10 minutos
-
Minutos 10 30-
-
Minutos 30 60-
-
horas 1-2
-
en más de 2 horas
-
otro
42 usuarios votaron. 47 usuarios se abstuvieron.
Fuente: habr.com