Kulisty nadmiar trójkąta

Jak wszyscy wiemy, suma kątów dowolnego płaskiego trójkąta jest równa 180 stopni.

Jednak w przypadku trójkąta sferycznego suma kątów jest zawsze większa niż 180 stopni. Różnica między sumą kątów sferycznych trójkątów a 180 stopni nazywa się nadwyżką sferyczną . Zadanie polega na obliczeniu sferycznego nadmiaru trójkąta z podanymi współrzędnymi wierzchołków.

Trochę tła

Trójkąt sferyczny jest częścią kuli wyznaczoną przez trzy wielkie koła kuli.

Zarówno boki, jak i kąty trójkąta sferycznego są mierzone jako miara kąta, ponieważ każdy bok można uznać za przecięcie kuli i pewien kąt płaski z wierzchołkiem w środku kuli:

Każde trzy odrębne wielkie koła definiują 8 trójkątów, ale bierzemy pod uwagę tylko właściwe trójkąty , tj. trójkąty, których kąt i wymiary boczne są spełnione

Wygodnie jest zdefiniować wierzchołki trójkąta pod względem geograficznego układu współrzędnych. Aby obliczyć długość łuku kuli, biorąc pod uwagę długość λ i szerokość geograficzną Φ jego końców, możemy użyć wzoru:

, gdzie

lub bardziej szczegółowo:

(źródło: https://en.wikipedia.org/wiki/Haversine_formula )

Dwie podstawowe formuły, których można użyć do rozwiązania trójkąta sferycznego, to:

• prawo cosinusów:

• prawo sinusów:

(źródło: https://en.wikipedia.org/wiki/Spherical_trigonometry#Cosine_rules_and_sine_rules )

Biorąc pod uwagę trzy strony, łatwo jest obliczyć kąty za pomocą reguły cosinus:

Na koniec określa się kulisty nadmiar trójkąta:

Co ciekawe w związku między sferycznym nadmiarem trójkąta a jego obszarem:

Zatem na kuli jednostkowej nadmiar trójkąta jest równy powierzchni tego trójkąta!

Zadanie

Napisz funkcję lub program, który oblicza sferyczny nadmiar trójkąta w stopniach, biorąc pod uwagę współrzędne wierzchołków trójkąta. Współrzędne wierzchołków podano w układzie współrzędnych geograficznych.

Każdy wierzchołek należy przekazać w formie [latitude in degrees][N|S][longitude in degrees][E|W]. Długość geograficzna i Elub Wmoże zostać pominięta, gdy szerokość wynosi 90, tj. 90N, 90S, 10N100E, 30S20WSą odpowiednie opisy wierzchołków, natomiast 80Nczy 55Snie.

Szerokość i długość geograficzna są zawsze liczbami całkowitymi w przypadkach testowych.

Odpowiedzi z błędem mniejszym niż jeden stopień zostaną zaakceptowane (jak w przykładach poniżej). Wynik może być zatem renderowany jako rzeczywisty lub całkowity, dla wygody użytkownika.

Przykłady

Wejście

90N0E
0N0E
0N90E

Wynik

89.999989

Wejście

90N
0N0E
0N90E

Wynik

89.999989

Wejście

0N0E
0N179E
90N0E

Wynik

178.998863

Wejście

10N10E
70N20W  
70N40E

Wynik

11.969793

We wszystkich przypadkach testowych długość i szerokość geograficzna są liczbami całkowitymi. Parsowania współrzędne wierzchołków jest częścią zadania, więc wierzchołek musi być przekazany jako jeden ciąg / dosłowny, nie wolno przechodzić 80N20Ejak cztery parametry / strun: 80, N, 20, E.

Gwarantuje to, że wszystkie wierzchołki są różne i żadne z trzech z trzech wierzchołków nie tworzy pary punktów antypodalnych.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod.

Matlab, 288 266 bajtów

Oto skomentowana wersja, która powinna wyjaśniać, co się dzieje:

                                  %parsing the input
for k=1:3;
    s=input('','s');              %request input
    if sum(s>57)<2;               %if we have only one letter, add arbitrary second coordinate
        s=[s,'0E'];
    end;
    S=1-2*(s(s>57)>80);           %calculate the sign of the coordinates
    s(s>57)=44;                   %replace letters with comma
    L(k,:)=eval(['[',s,']']).*S;  %evaluates string as list and multiply with signs
end;
i=[2,3,1];
                                  %calculate the angular distance between each pair of points
a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*pi/180;
                                  %evaluate the spherical excess
f=@(a,b,c)sum(acos((cos(a)-cos(b).*cos(c))./(sin(b).*sin(c))))-pi;
disp(f(a,a(i),a([3,1,2]))*180/pi)

W pełni golfowy (łamanie linii można usunąć):

for k=1:3;s=input('','s');if sum(s>57)<2;s=[s,'0E'];end;
s(s>57)=44;L(k,:)=eval([91,s,93]).*(1-2*(s(s<48)>80));end;
i=[2,3,1];p=pi/180;a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*p;
b=a(i);disp((sum(acos((cos(a([3,1,2]))-cos(b).*cos(a))./(sin(b).*sin(a))))-pi)/p)

Ruby, Rev 3 264 255 bajtów

Główne zmiany:

Nowa stała r= 180 / PI zdefiniowana i używana w całej funkcji. emusiał zostać zainicjowany na + PI, więc nadmiar odlicza się teraz w dół i jest negowany przed powrotem.

t[]wyeliminowane: Ruby pozwala t[]bezpośrednio przypisać dane, które zostały przypisaneu,v,w.

Pojedyncza ipętla do wykonania zadania dwóch ?:trójskładnikowych operatorów przełącza między zadaniami.

Wiele innych drobnych zmian.

include Math
->s{r=180/e=PI
x=y=z=n=[]
9.times{|i|i<6?(u,v,w=eval(?[+s[i%3].gsub(/[NE]/,"/r,").gsub(/[SW]/,"/-r,")+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u))+(y*=cos(v)*w=cos(u))+x*=w*sin(v)):e-=acos((n[i-7]-(c=n[i-6])*d=n[i-8])/sqrt((1-c*c)*(1-d*d)))}
-e*r}

Ruby, Rev 1 283 277 bajtów

Wymaga tablicy 3 ciągów.

include Math 
->s{x=y=z=n=[]
6.times{|i|t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))}
e=-PI
3.times{|i|e+=acos((n[i-1]-n[i]*d=n[i-2])/sqrt((1-n[i]**2)*(1-d**2)))}
e/PI*180}

Przegląd

Długości boków trójkąta na kuli jednostkowej są równe kątom między wektorami opisującymi dwa punkty. Ale nie musimy znać tego kąta. Wystarczy znać cosinus kąta, który można łatwo uzyskać ze współrzędnych kartezjańskich za pomocą iloczynu punktowego.

Wyjaśnienie

Ciągi wejściowe są konwertowane na ciąg znaków reprezentujący tablicę, która jest następnie analizowana i przechowywana t, jak poniżej. Ostatnie zero nie jest potrzebne, jeśli podano dwie współrzędne. Jeśli podana jest tylko szerokość geograficzna 90, zero jest interpretowane jako długość geograficzna.

Example:  70N20W --> [70*PI/180,20*-1*PI/180,0]

Produkty Dot mają formę a.b=ax*bx+ay*by+az*bz. Ponieważ wszystkie wektory mają długość jednostkową, iloczyn skalarny jest równy cosinusowi kąta między wektorami.

Aby je obliczyć, pętla jest iterowana 6 razy, przechodząc dwukrotnie przez dane wejściowe. Nawet w iteracjach 0,2,4 zmienne x,y,zsą ustawione na 1, aby rozpocząć nowe obliczenia. Podczas każdej iteracji zmienne te są mnożone przez składowe x, y i z każdego wektora, z wykorzystaniem danych długości i szerokości geograficznej przechowywanych w t[0],t[1](do których również przypisano golfa u,v). Suma zmiennych jest zapisywana do tablicy n(wartości śmieci w parzystych iteracjach są zastępowane poprawnymi wartościami w nieparzystych iteracjach), tak aby na końcu nzawierały produkty 3 kropkowe [a.b, c.a, b.c].

Aby zastosować regułę cosinus, potrzebujemy cosinus trzech zawartych kątów między wierzchołkami, ale potrzebujemy również sinusów. Są one uzyskiwane jako sqrt(1-cosine**2). W miarę mnożenia sinusów wyrażenie można zmienić, tak aby sqrtwymagane było tylko jedno wywołanie . Fakt, że nie wiemy, czy sinus był dodatni czy ujemny, nie ma znaczenia, ponieważ formuła haverine i tak zawsze daje sinus dodatni. Ważną wielkością fizyczną jest odległość między punktami, która jest absolutna, a zatem zawsze dodatnia.

Dla każdej iteracji i=0..2obliczamy wartość kąta przeciwnego elementu tablicy, i-1używając innych elementów ii i-2. Takie ujemne indeksy tablicowe takie jak ten są dozwolone w Rubim, po prostu zawijają się na początek tablicy.

Niegolfowany w programie testowym

Wymaga trzech zestawów współrzędnych na tej samej linii, z odstępami między nimi.

include Math
g=->s{
  n=[]         #array for dot products
  x=y=z=1      #it's required to use these variables once before the loop, for some bizarre reason
  6.times{|i|
    t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
    i%2<1&&x=y=z=1
    n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))
  }

  e=-PI        #set e to -PI and begin accumulating angles
  3.times{|i|
    e+=acos((n[i-1]-n[i]*n[i-2])/sqrt((1-n[i]**2)*(1-n[i-2]**2)))
  }

e/PI*180}      #return value

puts g[gets.split]