¿Qué tan iluminada está esta montaña? 🔥

62

Una montaña se define como un conjunto de segmentos de línea cuyo primer punto tiene coordenadas (0,a)donde a > 0, y cuyo último punto tiene coordenadas (b,0), dónde b > 0. Todos los puntos intermedios tienen una coordenada y (ordenada) estrictamente mayor que 0. Se le dan los puntos en la montaña ordenados en orden ascendente de la coordenada x (abscisa). Tenga en cuenta que dos puntos pueden tener la misma coordenada x, produciendo un segmento vertical de la montaña. Si se le dan dos puntos con la misma coordenada x, se deben conectar en el orden en que se dan. Además, puede haber segmentos horizontales de la montaña. Estos segmentos horizontales no están iluminados, pase lo que pase. Todas las coordenadas son enteros no negativos.

La pregunta: ¿cuál es la longitud total de la montaña que se iluminaría, suponiendo que el sol sea un plano de luz vertical infinito ubicado a la derecha de la montaña? Este número no necesita ser redondeado, pero si es redondeado, incluya al menos cuatro decimales. He incluido una imagen: La montaña aquí, las líneas en negrita representan los segmentos que están encendidos. Tenga en cuenta que en la entrada, P aparece antes que Q (PQ es un segmento de línea vertical), por lo que el punto anterior está conectado a P y no a Q.

Puede tomar la entrada en cualquier formato razonable, como una lista de listas, una sola lista, una cadena, etc.

Caso de prueba:

(0,3000)
(500, 3500)
(2500, 1000)
(5000,5000)
(9000,2000)
(9000,3500)
(10200,0)

Output: 6200.0000

Aquí hay dos segmentos iluminados, como se muestra en esta imagen: Test Case Pic el primero tiene una longitud de 5000/2 = 2500 y el segundo tiene una longitud de 3700.

Este es el , por lo que gana la respuesta más corta en bytes.

equipado
fuente
1
Sugerencia: Al encontrar la longitud de un segmento, hay tres puntos que debe considerar: los dos puntos finales y el punto que lo está "bloqueando" (en la segunda imagen, eso sería (9000,3500) que determina la longitud del segmento 3-4-5. Deje que los dos puntos en el segmento principal sean (x1, y1)y (x2,y2). El punto que está "bloqueando" es (x3, y3). Suponga que y2 <y3 <= y1. Entonces la longitud del segmento es ((y1 - y3)/(y1 - y2))*sqrt((x1 - x2)^2 + (y1 - y2)^2). fórmula de distancia, multiplicada por la fracción del segmento que se usa realmente.
aparejado el
1
¿Puede la montaña ser horizontal?
usuario202729
Sí, puede haber segmentos horizontales en la montaña. Sin embargo, irá a 0 en algún momento.
aparejado el
1
¿Pero deberían estar encendidos?
usuario202729
No están encendidos. La luz, siendo perfectamente horizontal, solo puede correr paralela a ellos y nunca golpearlos. Edité el problema para aclarar esto.
aparejado el

Respuestas:

14

Python 2 ,  134 131 128 124 120 117 109  107 bytes

p=input();s=0
for X,Y in p[1:]:x,y=p.pop(0);n=y-max(zip(*p)[1]);s+=n*(1+((X-x)/(y-Y))**2)**.5*(n>0)
print s

Pruébalo en línea!

Toma información como una lista de tuplas / listas de dos elementos de números de punto flotante.

Explicación

y1>y2for(x2,y2)(x1,y1)

Matemáticas: ¿qué parte del segmento de línea está expuesta a la luz?

Una montaña mal dibujada

(x1,y1)ymax(x2,y2)Lx3y1ymax

x3x2x1x3x2x1=y1ymaxy1x3=(y1ymax)(x2x1)y1

L=(y1ymax)2+x32

Al unir las dos fórmulas, llegamos a la siguiente expresión, que es el núcleo de este enfoque:

L=(y1ymax)2+((y1ymax)(x2x1)y1)2
L=(y1-ymetrounaX)2(1+(X2-X1)2y12)

Código - ¿Cómo funciona?

p=input();s=0                             # Assign p and s to the input and 0 respectively.
for X,Y in p[1:]:                         # For each point (X, Y) in p with the first
                                          # element removed, do:
    x,y=p.pop(0)                          # Assign (x, y) to the first element of p and
                                          # remove them from the list. This basically
                                          # gets the coordinates of the previous point.
    n=y-max(zip(*p)[1])                   # Assign n to the maximum height after the
                                          # current one, subtracted from y.
    s+=n*(1+((X-x)/(y-Y))**2)**.5         # Add the result of the formula above to s.
                                 *(n>0)   # But make it null if n < 0 (if y is not the
                                          # local maxima of this part of the graph).
print s                                   # Output the result, s.

Registro de cambios

  • Gradualmente optimizado la fórmula para fines de golf.

  • Guardado 1 byte gracias a FlipTack .

  • Se ahorraron 2 bytes al eliminar la condición innecesaria que y>Y, dado que si los máximos locales de la coordenada Y después del punto actual restado yson positivos, entonces esa condición es redundante. Sin embargo, esto desafortunadamente invalida el golf de FlipTack.

  • Guardamos 3 bytes cambiando un poco el algoritmo: en lugar de tener una variable de contador, incrementándola y siguiendo la lista, eliminamos el primer elemento en cada iteración.

  • Guardado 8 bytes gracias a ovs ; cambiando (x,y),(X,Y)en la condición del bucle con una list.pop()técnica.

  • Ahorró 2 bytes gracias a Ørjan Johansen (optimizó un poco la fórmula).

Sr. Xcoder
fuente
12

JavaScript, 97 bytes

a=>a.reduceRight(([p,q,l=0,t=0],[x,y])=>[x,y,y>t?(y-t)/(s=y-q)*Math.hypot(x-p,s)+l:l,y>t?y:t])[2]

f=a=>a.reduceRight(([p,q,l=0,t=0],[x,y])=>[x,y,y>t?(y-t)/(s=y-q)*Math.hypot(x-p,s)+l:l,y>t?y:t])[2];
t=[[0, 3000], [500, 3500], [2500, 1000], [5000, 5000], [9000, 2000], [9000, 3500], [10200, 0]];
console.log(f(t));

(Se pueden guardar 5 bytes si se considera válida la versión invertida de la entrada).

tsh
fuente
10

APL + WIN, 48 bytes

+/((h*2)+(((h←-2-/⌈\m)÷-2-/m←⌽⎕)×(⌽-2-/⎕))*2)*.5

Solicita una lista de coordenadas x seguida de una lista de coordenadas y

Explicación

h←-2-/⌈\m difference between successive vertical maxima viewed from the right (1)

-2-/m←⌽⎕ vertical difference between points (2)

⌽-2-/⎕ horizontal difference between points (3)

Las distancias verticales iluminadas = h y las distancias horizontales iluminadas son (3) * (1) / (2). El resto es Pitágoras.

Graham
fuente
Funcionaria +/.5*⍨(h*2)+×⍨((h←-2-/⌈\m)÷-2-/m←⌽⎕)×⌽-2-/⎕?
Kritixi Lithos
Por desgracia mi vieja versión de APL + WIN no tiene el operador, de modo que no puedo decir
Graham
@Cows quack Gestionado para probarlo en una versión antigua de Dyalog Unicode (v13) y su sugerencia funciona
Graham
6

Swift , 190 bytes

import Foundation
func f(a:[(Double,Double)]){var t=0.0,h=t,l=(t,t)
a.reversed().map{n in if l.0>=n.0&&n.1>l.1{t+=max((n.1-h)/(n.1-l.1)*hypot(n.0-l.0,n.1-l.1),0)
h=max(n.1,h)}
l=n}
print(t)}

Pruébalo en línea!

Explicación

import Foundation                  // Import hypot() function
func f(a:[(Double,Double)]){       // Main function
  var t=0.0,h=0.0,l=(0.0,0.0)      // Initialize variables
  a.reversed().map{n in            // For every vertex in the list (from right to left):
    if l.0>=n.0&&n.1>l.1{          //   If the line from the last vertex goes uphill:
      t+=max((n.1-h)/(n.1-l.1)     //     Add the fraction of the line that's above the
        *hypot(n.0-l.0,n.1-l.1),0) //     highest seen point times the length of the line
                                   //     to the total
      h=max(n.1,h)}                //     Update the highest seen point
    l=n}                           //   Update the last seen point
  print(t)}                        // Print the total
Herman L
fuente
5

Python 2 , 122 120 bytes

k=input()[::-1]
m=r=0
for(a,b),(c,d)in zip(k,k[1:]):
 if d>m:r+=(b>=m or(m-b)/(d-b))*((a-c)**2+(b-d)**2)**.5;m=d
print r

Pruébalo en línea!

ovs
fuente
Como se nos permite tomar una lista de valores xy una lista de valores y como dos entradas, estoy bastante seguro de que podríamos tomar una lista de coordenadas a la inversa, eliminando la necesidad de [::-1].
Jonathan Allan
3

Python 2 , 89 bytes

M=t=0
for x,y in input()[::-1]:
 if y>M:t+=(y-M)*abs((x-X)/(y-Y)+1j);M=y
 X,Y=x,y
print t

Pruébalo en línea!

Toma una lista de pares de carrozas. Basado en la solución de ovs .

xnor
fuente
Cree que podemos tomar una lista inversa (se nos permite tomar x e y como listas separadas), por lo que puede descartar la [::-1].
Jonathan Allan
1

APL (Dyalog Unicode) , SBCS de 31 bytes

Utiliza la fórmula de Graham .

Función de prefijo anónimo que toma una matriz de datos 2 × n como argumento correcto. La primera fila contiene valores x de derecha a izquierda, y la segunda fila los valores y correspondientes.

{+/.5*⍨(×⍨2-/⌈\2⌷⍵)×1+×⍨÷⌿2-/⍵}

Pruébalo en línea!

{... } anónimo lambda donde está el argumento:

2-/⍵ deltas (lit. por parejas menos reducciones)

÷⌿ΔxΔy (lit. reducción de división vertical)

×⍨ cuadrado (literalmente, multiplicación selfie)

1+ uno agregado a eso

(...  multiplique lo siguiente con eso:

  2⌷⍵ segunda fila del argumento (los valores y)

  ⌈\ máximo de carrera (altura más alta alcanzada hasta ahora, yendo desde la derecha)

  2-/ deltas de (lit. por pares menos reducción)

  ×⍨ cuadrado (literalmente, multiplicación selfie)

.5*⍨raíz cuadrada (literalmente, eleva eso a la potencia de la mitad)

+/ suma

Adán
fuente
1

Jalea , 23 bytes

ṀÐƤḊ_⁸«©0×⁹I¤÷⁸I¤,®²S½S

Un enlace diádico que toma una lista de valores de y a la izquierda y una lista de los respectivos valores de x a la derecha (como lo permite explícitamente el OP en los comentarios)

Pruébalo en línea!

¿Cómo?

La fracción de una sección (inclinada) que se ilumina es la misma fracción que se iluminaría si fuera una caída vertical. Tenga en cuenta que, dado que se produce la cuadratura para evaluar las longitudes de las pendientes, las alturas calculadas a lo largo del camino pueden ser negativas (también en el siguiente, las longitudes de recorrido de las pendientes iluminadas se calculan como negativas divididas por negativas).

ṀÐƤḊ_⁸«©0×⁹I¤÷⁸I¤,®²S½S - Link:list, yValues; list, xValues
 ÐƤ                     - for suffixes of the yValues:       e.g. [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
Ṁ                       -   maximum                               [ 5000, 5000, 5000, 5000, 3500, 3500,    0]
   Ḋ                    - dequeue                                 [ 5000, 5000, 5000, 3500, 3500,    0]
     ⁸                  - chain's left argument, yValues          [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
    _                   - subtract                                [ 2000, 1500, 4000,-1500, 1500,-3500,    0]
        0               - literal zero
      «                 - minimum (vectorises)                    [    0,    0,    0,-1500,    0,-3500,    0]
       ©                - copy to the register for later
            ¤           - nilad followed by link(s) as a nilad:
          ⁹             -   chain's right argument, xValues  e.g. [    0,  500, 2500, 5000, 9000, 9000, 10200]
           I            -   incremental differences               [  500, 2000, 2500, 4000,    0, 1200]
         ×              - multiply (vectorises)                   [    0,    0,    0,-6000000, 0,-4200000, 0]
                ¤       - nilad followed by link(s) as a nilad:
              ⁸         -   chain's left argument, yValues        [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
               I        -   incremental differences               [  500,-2500, 4000,-3000, 1500,-3500]
             ÷          - divide (vectorises)                     [    0,    0,    0, 2000,    0, 1200,    0]
                  ®     - recall from the register                [    0,    0,    0,-1500,    0,-3500,    0]
                 ,      - pair (i.e. lit slope [runs, rises])     [[0, 0, 0,    2000, 0,    1200, 0], [0, 0, 0,   -1500, 0,    -3500, 0]]
                   ²    - square (vectorises)                     [[0, 0, 0, 4000000, 0, 1440000, 0], [0, 0, 0, 2250000, 0, 12250000, 0]]            
                    S   - sum (vectorises)                        [  0,   0,   0, 6250000,   0, 13690000,   0]
                     ½  - square root (vectorises)                [0.0, 0.0, 0.0,  2500.0, 0.0,   3700.0, 0.0]
                      S - sum                                     6200.0

Versión monádica de 25 bytes que toma una lista de [x,y]coordenadas:

ṀÐƤḊ_«0
Z©Ṫµ®FI×Ç÷I,DzS½S

Prueba este.

Jonathan Allan
fuente
1
La entrada puede ser dos listas de valores. Le pregunté al OP hace un tiempo y dijeron que está bien .
Sr. Xcoder
Siento que hay demasiados s y s.
Jonathan Allan
0

Kotlin , 178 bytes

fun L(h:List<List<Double>>)=with(h.zip(h.drop(1))){mapIndexed{i,(a,b)->val t=a[1]-drop(i).map{(_,y)->y[1]}.max()!!;if(t>0)t*Math.hypot(1.0,(a[0]-b[0])/(a[1]-b[1]))else .0}.sum()}

Pruébalo en línea!

La parte de prueba es mucho menos golf :)

Damiano
fuente