Jak oświetlona jest ta góra? 🔥

62

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: Góra 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: Przypadek testowy Pierwszy ma długość 5000/2 = 2500, a drugi ma długość 3700.

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

takielunek
źródło
1
Wskazówka: przy ustalaniu długości odcinka należy wziąć pod uwagę trzy punkty: dwa punkty końcowe i punkt, który go „blokuje” (na drugim zdjęciu, to byłby (9000,3500), który określa długość z segmentu 3-4-5. Niech dwoma punktami w głównym segmencie będą (x1, y1)i (x2,y2). Punktem, który „blokuje” jest (x3, y3). Załóżmy, że y2 <y3 <= y1. Zatem długość segmentu to ((y1 - y3)/(y1 - y2))*sqrt((x1 - x2)^2 + (y1 - y2)^2). Jest to zasadniczo wzór na odległość pomnożony przez ułamek faktycznie używanego segmentu
takielunek
1
Czy góra może być pozioma?
user202729,
Tak, na górze mogą znajdować się poziome segmenty. Jednak w pewnym momencie spadnie do 0.
sfałszowany
1
Ale czy powinny być zapalone?
user202729,
Nie są zapalone. Światło, będąc idealnie poziomym, może biegać tylko równolegle do nich i nigdy ich nie uderzać. Zredagowałem problem, aby to wyjaśnić.
sfałszowany

Odpowiedzi:

14

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 .y1>y2for(x2,y2)(x1,y1)

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

Źle narysowana góra

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.(x1,y1)ymax(x2,y2)Lx3y1ymax

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:x3x2x1x3x2x1=y1ymaxy1x3=(y1ymax)(x2x1)y1

L=(y1ymax)2+x32

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

L=

L=(y1ymax)2+((y1ymax)(x2x1)y1)2
L=(y1ymax)2(1+(x2x1)2y12)

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łę).

Pan Xcoder
źródło
12

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

tsh
źródło
10

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.

Graham
źródło
Czy +/.5*⍨(h*2)+×⍨((h←-2-/⌈\m)÷-2-/m←⌽⎕)×⌽-2-/⎕zadziała?
Kritixi Lithos
Niestety moja stara wersja APL + WIN nie ma operatora, więc nie mogę powiedzieć
Graham,
@ Cows quack Udało się wypróbować go w starej wersji Dyalog Unicode (v13), a twoja sugestia działa
Graham
6

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
Herman L.
źródło
5

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!

ovs
źródło
Ponieważ możemy wziąć listę wartości x i listę wartości y jako dwa dane wejściowe, jestem prawie pewien, że moglibyśmy wziąć listę współrzędnych w odwrotnej kolejności, eliminując potrzebę [::-1].
Jonathan Allan
2

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 .

xnor
źródło
Pomyśl, że możemy wziąć odwrotną listę (możemy wziąć xiy jako osobne listy), więc możesz upuścić [::-1].
Jonathan Allan
1

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

Adám
źródło
1

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.

Jonathan Allan
źródło
1
Dane wejściowe mogą stanowić dwie listy wartości. Jakiś czas temu poprosiłem OP, a oni powiedzieli , że to w porządku .
Pan Xcoder,
Czuję się tam zbyt wiele s i s.
Jonathan Allan
0

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

Damiano
źródło