Góra jest zdefiniowana jako zbiór odcinków, których pierwszy punkt ma współrzędne (0,a)miarę a > 0, i którego ostatni punkt ma współrzędne (b,0), gdzie b > 0. Wszystkie punkty pośrednie mają współrzędną y (rzędną) ściśle większą niż 0. Dostajesz punkty na górze posortowane w porządku rosnącym współrzędnych x (odcięta). Zauważ, że dwa punkty mogą mieć tę samą współrzędną x, tworząc pionowy odcinek góry. Jeśli otrzymasz dwa punkty o tej samej współrzędnej x, należy je połączyć w podanej kolejności. Ponadto mogą istnieć poziome segmenty góry. Te poziome segmenty nie są oświetlone, bez względu na wszystko. Wszystkie współrzędne są liczbami całkowitymi nieujemnymi.

Pytanie: jaka jest całkowita długość góry, która byłaby oświetlona, ​​zakładając, że słońce jest nieskończoną pionową płaszczyzną światła usytuowaną na prawo od góry? Liczby tej nie trzeba zaokrąglać, ale jeśli jest zaokrąglona, ​​należy podać co najmniej cztery miejsca po przecinku. Zawarłem zdjęcie: pogrubione linie reprezentują podświetlone segmenty. Zauważ, że na wejściu P pojawia się przed Q (PQ jest pionowym odcinkiem linii), więc poprzedni punkt jest podłączony do P, a nie do Q.

Możesz przyjmować dane wejściowe w dowolnym rozsądnym formacie, takim jak lista list, pojedyncza lista, ciąg znaków itp.

Przypadek testowy:

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

Output: 6200.0000

Są tutaj dwa podświetlone segmenty, jak pokazano na tym obrazku: Pierwszy ma długość 5000/2 = 2500, a drugi ma długość 3700.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Python 2 ,  134 131 128 124 120 117 109  107 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako listę krotek / dwuelementowych list liczb zmiennoprzecinkowych.

Wyjaśnienie

Zasadniczo iterujemy przez pary punktów na wykresie, a jeśli , obliczamy, ile linii jest wystawiane na działanie światła. Iteracja par wykonywana jest za pomocą pętli, aby uzyskać następny punkt , za każdym razem pierwszy element na liście, aby pobrać bieżący punkt .$y_1 > y_2$for$(x_2, y_2)$$(x_1, y_1)$

Matematyka - Jaka część segmentu linii jest wystawiona na światło?

Niech będą współrzędnymi bieżącego punktu. Niech maksymalną wysokością punktu za bieżącym (lokalne maksima za bieżącym punktem), a będą współrzędnymi następnego punktu. Aby obliczyć długość wystawioną na słońce, , powinniśmy znaleźć , jak pokazano na schemacie. Oczywiście, jeśli , segment w ogóle nie będzie wystawiony na działanie światła.$(x_1, y_1)$$y_{max}$$(x_2, y_2)$$L$$x_3$$y_1 \le y_{max}$

W utworzonym trójkącie odcinek linii o długości jest równoległy do ​​podstawy o długości , więc wszystkie trzy kąty są zgodne. Dlatego z Podstawowego twierdzenia podobieństwa (przypadek Kąt-kąt) możemy wywnioskować, że . Dlatego . Następnie możemy zastosować twierdzenie Pitagorasa, aby stwierdzić, że:$x_3$$x_2 - x_1$$\frac{x_3}{x_2 - x_1} = \frac{y_1-y_{max}}{y_1}$$x_3 = \frac{(y_1-y_{max})(x_2 - x_1)}{y_1}$

Łącząc te dwie formuły, dochodzimy do następującego wyrażenia, które jest rdzeniem tego podejścia:

L=

Kod - jak to działa?

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.

Dziennik zmian

• Stopniowo zoptymalizowano formułę do gry w golfa.

• Oszczędność 1 bajtu dzięki FlipTack .

• Zaoszczędzono 2 bajty, usuwając niepotrzebny warunek y>Y, ponieważ ponieważ lokalne maksima współrzędnej Y po odjęciu bieżącego punktu ysą dodatnie, warunek ten jest zbędny. To niestety unieważnia grę w golfa FlipTack.

• Zaoszczędziliśmy 3 bajty, zmieniając nieco algorytm: zamiast zmiennej licznika, zwiększając ją i dostosowując listę, usuwamy pierwszy element przy każdej iteracji.

• Zaoszczędzono 8 bajtów dzięki ovs ; zmiana (x,y),(X,Y)stanu pętli za pomocą list.pop()techniki.

• Zaoszczędził 2 bajty dzięki Ørjan Johansen (nieco zoptymalizował formułę).

JavaScript, 97 bajtów

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));

(Można zapisać 5 bajtów, jeśli przyjęcie odwróconej wersji danych wejściowych zostanie uznane za prawidłowe.)

APL + WIN, 48 bajtów

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

Monituje o listę współrzędnych x, a następnie listę współrzędnych y

Wyjaśnienie

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)

Świecone odległości pionowe = h, a oświetlone odległości poziome wynoszą (3) * (1) / (2). Reszta to Pitagoras.

Szybki , 190 bajtów

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)}

Wypróbuj online!

Wyjaśnienie

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

Python 2 , 122 120 bajtów

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

Wypróbuj online!

Python 2 , 89 bajtów

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

Wypróbuj online!

Zawiera listę par pływaków. Na podstawie rozwiązania ovs .

APL (Dyalog Unicode) , 31 bajtów ^SBCS

Wykorzystuje formułę Grahama .

Anonimowa funkcja prefiksu przyjmująca macierz danych 2 × n jako właściwy argument. Pierwszy wiersz zawiera wartości x od prawej do lewej, a drugi wiersz odpowiada odpowiednim wartościom y.

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

Wypróbuj online!

{… } Anonimowa lambda gdzie ⍵jest argument:

 2-/⍵ delty (litowo minusowe redukcje)

 ÷⌿ ^Δx ⁄ _Δy ( _{podświetlone} zmniejszenie podziału pionowego)

 ×⍨ kwadrat (oświetlone selfie z mnożeniem)

 1+ jeden do tego dodany

 (… )× Pomnóż przez to:

  2⌷⍵ drugi wiersz argumentu (wartości y)

  ⌈\ bieganie maksimum (najwyższa osiągnięta do tej pory, idąc od prawej)

  2-/ delty (litera minus minus redukcja)

  ×⍨ kwadrat (oświetlone selfie z mnożeniem)

 .5*⍨pierwiastek kwadratowy (dosł. zwiększ to do potęgi połowy)

 +/ suma

Galaretka , 23 bajty

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

Dyadyczny link pobierający listę wartości y po lewej stronie i listę odpowiednich wartości x po prawej stronie (co wyraźnie dozwolone przez OP w komentarzach)

Wypróbuj online!

W jaki sposób?

Frakcja oświetlonego odcinka (pochyłego) jest tą samą frakcją, która byłaby oświetlona, ​​gdyby był to pionowy spadek. Zauważ, że ponieważ do oceny długości nachylenia dochodzi do kwadratu, obliczone wysokości po drodze mogą być ujemne (również poniżej długości przebiegów oświetlonych stoków są obliczane jako ujemne podzielone przez ujemne).

ṀÐƤḊ_⁸«©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

25-bajtowa wersja monadyczna z listą [x,y]współrzędnych:

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

Spróbuj tego.

Kotlin , 178 bajtów

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()}

Wypróbuj online!

Część testowa jest bardzo nie golfa :)