Wie hell ist dieser Berg? 🔥

62

Ein Berg ist definiert als eine Menge von Liniensegmenten, deren erster Punkt Koordinaten hat, (0,a)wo a > 0und deren letzter Punkt Koordinaten hat (b,0), wo b > 0. Alle Zwischenpunkte haben eine y-Koordinate (Ordinate), die streng größer als 0 ist. Sie erhalten die Punkte auf dem Berg in aufsteigender Reihenfolge der x-Koordinate (Abszisse) sortiert. Beachten Sie, dass zwei Punkte dieselbe x-Koordinate haben können, wodurch ein vertikaler Abschnitt des Berges erzeugt wird. Wenn Sie zwei Punkte mit derselben x-Koordinate erhalten, sollten diese in der angegebenen Reihenfolge verbunden werden. Außerdem kann es horizontale Segmente des Berges geben. Diese horizontalen Segmente werden auf keinen Fall beleuchtet. Alle Koordinaten sind nicht negative Ganzzahlen.

Die Frage: Was ist die Gesamtlänge des Berges, der beleuchtet werden wßrde, vorausgesetzt, die Sonne ist eine unendliche vertikale Lichtebene rechts vom Berg? Diese Zahl muss nicht gerundet werden. Wenn sie jedoch gerundet ist, mßssen mindestens vier Dezimalstellen angegeben werden. Ich habe ein Bild beigefßgt: Der Berg Hier stellen die Linien, die fett gedruckt sind, die Segmente dar, die beleuchtet sind. Beachten Sie, dass P in der Eingabe vor Q steht (PQ ist ein vertikales Liniensegment), sodass der vorherige Punkt mit P und nicht mit Q verbunden ist.

Sie kĂśnnen Eingaben in jedem vernĂźnftigen Format vornehmen, z. B. in Form einer Liste von Listen, einer einzelnen Liste, einer Zeichenfolge usw.

Testfall:

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

Output: 6200.0000

Hier gibt es zwei beleuchtete Segmente, wie in diesem Bild gezeigt: Testfall Abb Das erste hat eine Länge von 5000/2 = 2500 und das zweite eine Länge von 3700.

Das ist , also gewinnt die kĂźrzeste Antwort in Bytes.

manipulierten
quelle
1
Hinweis: Wenn Sie die Länge eines Segments ermitteln, müssen Sie drei Punkte berücksichtigen: die beiden Endpunkte und den Punkt, der es "blockiert" (im zweiten Bild wäre das (9000,3500), der die Länge bestimmt) das 3-4-5 - Segments. die zwei Punkte auf dem Hauptsegment Let sein (x1, y1)und (x2,y2). den Punkt, wird als „Blockieren“ ist (x3, y3). es sei angenommen , y2 <y3 <= y1. Dann wird die Länge des Segments ((y1 - y3)/(y1 - y2))*sqrt((x1 - x2)^2 + (y1 - y2)^2). Dies ist im wesentlichen der Entfernungsformel, multipliziert mit dem Bruchteil des tatsächlich verwendeten Segments
manipuliert
1
Darf der Berg waagerecht sein?
user202729
Ja, es kann horizontale Segmente auf dem Berg geben. Es wird jedoch irgendwann auf 0 gehen.
22.12.17
1
Aber sollten sie angezĂźndet werden?
user202729
Sie leuchten nicht. Das Licht, das vollkommen horizontal ist, kann nur parallel zu ihnen verlaufen und sie niemals treffen. Ich habe das Problem bearbeitet, um dies zu klären.
manipuliert

Antworten:

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

Probieren Sie es online!

Übernimmt die Eingabe als Liste von Tupeln / Listen mit zwei Elementen von Gleitkommazahlen.

Erläuterung

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

Mathematik - Welcher Teil des Liniensegments ist Licht ausgesetzt?

Ein schlecht gezeichneter Berg

(x1,y1)ymax(x2,y2)Lx3y1≤ymax

x3x2−x1x3x2−x1=y1−ymaxy1x3=(y1−ymax)(x2−x1)y1

L=(y1−ymax)2+x32

Durch Verbinden der beiden Formeln erhalten wir den folgenden Ausdruck, der den Kern dieses Ansatzes bildet:

L=(y1−ymax)2+((y1−ymax)(x2−x1)y1)2
L=(y1−ymax)2(1+(x2−x1)2y12)

Code - Wie funktioniert es?

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.

Änderungsprotokoll

  • Allmählich die Formel fĂźr Golfzwecke optimiert.

  • 1 Byte dank FlipTack gespeichert .

  • 2 Bytes gespart durch Entfernen der unnĂśtigen Bedingung, dass diese Bedingung redundant ist y>Y, wenn die lokalen Maxima der Y- Koordinate nach dem aktuellen Punkt, von dem abgezogen wurde, ypositiv sind. Dies macht das Golfspiel von FlipTack leider ungĂźltig.

  • Einsparung von 3 Bytes durch geringfĂźgige Änderung des Algorithmus: Anstatt eine Zählervariable zu haben, diese zu erhĂśhen und die Liste zu erweitern, wird bei jeder Iteration das erste Element entfernt.

  • 8 Bytes dank ovs gespart ; Ändern (x,y),(X,Y)der Schleifenbedingung mit einer list.pop()Technik.

  • 2 Bytes gespart dank Ørjan Johansen (Formel etwas optimiert).

Mr. Xcoder
quelle
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));

(5 Bytes kĂśnnen gespeichert werden, wenn die Verwendung der umgekehrten Eingabeversion als gĂźltig angesehen wird.)

tsh
quelle
10

APL + WIN, 48 Bytes

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

Fordert zur Eingabe einer Liste mit x-Koordinaten gefolgt von einer Liste mit y-Koordinaten auf

Erläuterung

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)

Die beleuchteten vertikalen Abstände = h und die beleuchteten horizontalen Abstände betragen (3) * (1) / (2). Der Rest ist Pythagoras.

Graham
quelle
Würde +/.5*⍨(h*2)+×⍨((h←-2-/⌈\m)÷-2-/m←⌽⎕)×⌽-2-/⎕funktionieren
Kritixi Lithos
Leider hat meine alte APL + WIN-Version keinen ⍨Operator, daher kann ich nicht sagen
Graham
@Cows quack Schaffte es, es in einer alten Version von Dyalog Unicode (v13) zu versuchen und Ihr Vorschlag funktioniert
Graham
6

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

Probieren Sie es online!

Erläuterung

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
quelle
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

Probieren Sie es online!

ovs
quelle
Da wir eine Liste von x-Werten und eine Liste von y-Werten als zwei Eingaben verwenden dĂźrfen, bin ich mir ziemlich sicher, dass wir eine Liste von Koordinaten in umgekehrter Reihenfolge erstellen kĂśnnen, ohne dass dies erforderlich ist [::-1].
Jonathan Allan
2

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

Probieren Sie es online!

Nimmt eine Liste von Schwimmerpaaren auf. Basierend auf der LĂśsung von ovs .

xnor
quelle
Denken Sie, wir kĂśnnen eine umgekehrte Liste erstellen (wir dĂźrfen x und y als separate Listen verwenden), damit Sie die Liste lĂśschen kĂśnnen [::-1].
Jonathan Allan
1

APL (Dyalog Unicode) , 31 Byte SBCS

Verwendet Grahams Formel .

Anonyme Präfixfunktion, die eine 2 × n-Datenmatrix als rechtes Argument verwendet. Die erste Zeile enthält x-Werte von rechts nach links und die zweite Zeile die entsprechenden y-Werte.

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

Probieren Sie es online!

{… } Anonymer Lambda wo ⍵ist das Argument:

 2-/⍵ Deltas (paarweise minus-Reduktionen)

 ÷⌿ Δx ⁄ Δy (lit. vertikale Teilungsreduktion)

 ×⍨ Quadrat (Lit. Multiplikation Selfie)

 1+ man fügte hinzu

 (… )× Multipliziere folgendes damit:

  2⌷⍵ zweite Zeile des Arguments (die y-Werte)

  ⌈\ Laufmaximum (höchste bisher erreichte Höhe von rechts)

  2-/ Deltas von (paarweise minus-Reduktion)

  ×⍨ Quadrat (Lit. Multiplikation Selfie)

 .5*⍨Quadratwurzel (wörtlich: halbe Potenz)

 +/ Summe

Adam
quelle
1

Jelly , 23 Bytes

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

Ein dyadischer Link mit einer Liste von y-Werten links und einer Liste der entsprechenden x-Werte rechts (wie vom OP in Kommentaren ausdrĂźcklich erlaubt)

Probieren Sie es online!

Wie?

Der Bruchteil eines (abfallenden) Abschnitts, der beleuchtet wird, ist derselbe Bruchteil, der beleuchtet wßrde, wenn es sich um einen vertikalen Abfall handeln wßrde. Beachten Sie, dass die berechneten HÜhen auf dem Weg negativ sein kÜnnen, da eine Quadrierung auftritt, um die Neigungslängen zu bewerten (auch im Folgenden werden die Lauflängen der beleuchteten Neigungen als negativ geteilt durch negativ berechnet).

ṀÐƤḊ_⁸«©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-Byte-Monadic-Version mit einer Liste von [x,y]Koordinaten:

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

Probier diese.

Jonathan Allan
quelle
1
Die Eingabe kann aus zwei Wertelisten bestehen. Ich habe vor einiger Zeit beim OP nachgefragt und sie sagten, dass es in Ordnung ist .
Mr. Xcoder
Ich habe das Gefßhl, es gibt zu viele ⁸s und ⁚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()}

Probieren Sie es online!

Der Testteil ist sehr viel nicht golfen :)

Damiano
quelle