Sebuah gunung didefinisikan sebagai satu set segmen garis yang pertama titik memiliki koordinat (0,a)di mana a > 0, dan yang terakhir titik memiliki koordinat (b,0), di mana b > 0. Semua titik antara memiliki koordinat y (ordinat) yang benar-benar lebih besar dari 0. Anda diberi titik di gunung yang diurutkan dalam urutan koordinat x (abscissa). Perhatikan bahwa dua titik dapat memiliki koordinat x yang sama, menghasilkan segmen vertikal gunung. Jika Anda diberi dua poin dengan koordinat x yang sama, mereka harus terhubung dalam urutan yang diberikan. Selain itu, mungkin ada segmen horisontal dari gunung. Segmen horizontal ini tidak menyala, apa pun yang terjadi. Semua koordinat adalah bilangan bulat tidak negatif.

Pertanyaannya: berapa panjang total gunung yang akan dinyalakan, dengan asumsi matahari adalah bidang cahaya vertikal tak terbatas yang terletak di sebelah kanan gunung? Angka ini tidak perlu dibulatkan, tetapi jika dibulatkan, sertakan setidaknya empat tempat desimal. Saya telah menyertakan gambar: Di sini, garis-garis yang dicetak tebal mewakili segmen yang menyala. Perhatikan bahwa dalam input, P muncul sebelum Q (PQ adalah segmen garis vertikal) sehingga titik sebelumnya terhubung ke P dan bukan Q.

Anda dapat mengambil input dalam format yang masuk akal, seperti daftar daftar, satu daftar, string, dll.

Kasus cobaan:

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

Output: 6200.0000

Ada dua segmen yang menyala di sini, seperti yang ditunjukkan pada gambar ini: Yang pertama memiliki panjang 5000/2 = 2500 dan yang kedua memiliki panjang 3.700.

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

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

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

Cobalah online!

Mengambil input sebagai daftar tupel / daftar elemen dua angka floating-point.

Penjelasan

Kami pada dasarnya beralih melalui pasangan titik dalam grafik, dan jika , maka kami menghitung berapa banyak garis yang terpapar cahaya. Iterasi berpasangan dilakukan dengan lingkaran untuk mendapatkan titik berikutnya, ( x 2 , y 2 ) , muncul elemen pertama dalam daftar setiap kali untuk mengambil titik saat ini, ( x 1 , y 1 ) .$y_1 > y_2$for$(x_2, y_2)$$(x_1, y_1)$

Matematika - Bagian segmen garis apa yang terpapar cahaya?

$(x_1, y_1)$$y_{max}$$(x_2, y_2)$$L$$x_3$$y_1 \le y_{max}$

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

Dengan bergabung dengan dua formula, kita sampai pada ungkapan berikut, yang merupakan inti dari pendekatan ini:

Kode - Bagaimana cara kerjanya?

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.

Changelog

• Formula yang dioptimalkan secara bertahap untuk tujuan bermain golf.

• Disimpan 1 byte berkat FlipTack .

• Menyelamatkan 2 byte dengan menghapus kondisi yang tidak perlu itu y>Y, karena jika maksimum lokal Y- koordinat setelah titik saat ini dikurangi dari ypositif, maka kondisi itu berlebihan. Sayangnya ini membatalkan golf FlipTack.

• Disimpan 3 byte dengan mengubah sedikit algoritme: alih-alih memiliki variabel penghitung, menambahkannya dan mengikuti daftar, kami menghapus elemen pertama di setiap iterasi.

• Disimpan 8 byte berkat ovs ; mengubah (x,y),(X,Y)kondisi loop dengan list.pop()teknik.

• Disimpan 2 byte berkat Ørjan Johansen (dioptimalkan sedikit rumus).

JavaScript, 97 byte

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

(5 byte dapat disimpan, jika mengambil versi input yang terbalik dianggap valid.)

APL + WIN, 48 byte

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

Anjuran untuk daftar koordinat x diikuti oleh daftar koordinat y

Penjelasan

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)

Jarak vertikal yang menyala = h dan jarak horizontal yang menyala adalah (3) * (1) / (2). Sisanya adalah Pythagoras.

Swift , 190 byte

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

Cobalah online!

Penjelasan

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 byte

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

Cobalah online!

Python 2 , 89 byte

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

Cobalah online!

Mengambil daftar pasang pelampung. Didasarkan pada solusi ovs .

APL (Dyalog Unicode) , 31 byte ^SBCS

Menggunakan formula Graham .

Fungsi awalan anonim mengambil 2 x n matriks data sebagai argumen yang benar. Baris pertama berisi nilai-x dari kanan ke kiri, dan baris kedua berisi nilai-y.

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

Cobalah online!

{… } Lambda anonim di mana ⍵argumennya:

 2-/⍵ delta (lit. minus-reduksi berpasangan)

 ÷⌿ ^Δx ⁄ _Δy (pengurangan divisi vertikal lit.)

 ×⍨ square (lit. selfie perkalian)

 1+ satu ditambahkan ke itu

 (... )× gandakan yang berikut dengan itu:

  2⌷⍵ baris kedua argumen (nilai y)

  ⌈\ menjalankan maksimum (ketinggian tertinggi bertemu sampai sekarang, dari kanan)

  2-/ delta (lit. berpasangan minus-reduksi)

  ×⍨ square (lit. selfie perkalian)

 .5*⍨akar kuadrat (lit. naikkan ke kekuatan setengah)

 +/ jumlah

Jelly , 23 byte

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

Tautan diad mengambil daftar nilai y di sebelah kiri dan daftar masing-masing nilai x di sebelah kanan (seperti yang secara eksplisit diizinkan oleh OP dalam komentar)

Cobalah online!

Bagaimana?

Fraksi dari bagian (miring) yang menyala adalah fraksi yang sama yang akan menyala jika itu adalah penurunan vertikal. Perhatikan bahwa karena kuadrat terjadi untuk mengevaluasi panjang lereng, ketinggian yang dihitung sepanjang jalan bisa negatif (juga di bawah panjang run dari lereng yang menyala dihitung sebagai negatif dibagi dengan negatif).

ṀÐƤḊ_⁸«©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 monadik 25 byte yang mengambil daftar [x,y]koordinat:

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

Coba yang ini.

Kotlin , 178 byte

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

Cobalah online!

Bagian pengujian sangat tidak golf :)