Jesteś właścicielem restauracji. Otwieracie się w nowym obszarze w Kartezji, gdzie jest tylko jedna główna droga, znana jako oś Y. Chcesz umieścić swoją restaurację w taki sposób, aby zminimalizować całkowitą odległość od restauracji i każdego domu w tym obszarze.

Wejście :

Dane wejściowe będą

n, the number of houses
house1
house2
house3
...
houseN

gdzie każdy dom jest współrzędną w formularzu x y. Każda jednostka reprezentuje jeden kilometr.

Możesz wziąć dane wejściowe jako ciąg znaków lub podać funkcję, która pobiera dane wejściowe, w dowolnym wybranym formacie, jako argumenty.

Wyjście : współrzędna y twojej restauracji (pamiętaj, że będzie ona znajdować się na osi y). W rzeczywistości będzie znajdować się na poboczu drogi, ale różnica jest znikoma.

Zasadniczo, jeśli n-ty dom jest h_ni Djest funkcją odległości, to chcesz znaleźćk taką, która D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k))jest zminimalizowana.

Należy pamiętać, że odległość jest obliczana tak, jakby klient podróżował w dokładnie prostej linii od domu do restauracji. To jest odległość od(x, y) twojej restauracji sqrt(x^2 + (y - k)^2).

Dane wyjściowe powinny być dokładne z dokładnością do co najmniej 2 miejsc po przecinku.

Dane wyjściowe mogą być drukowane jako ciąg znaków lub mogą być zwracane z funkcji.

Przykładowe wejście / wyjście:

Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

Całkowita odległość w tym przykładzie wynosi około 15.4003 kilometrów.

To jest kod golfowy - wygrywa najkrótszy kod.

PS Interesuje mnie również matematyczne rozwiązanie, które nie jest tylko brutalną siłą. Nie wygra golfa kodowego, ale zyska trochę aprobaty. Oto jak zrobiłem przykładowy problem:

Niech punkt A będzie zlokalizowany na A (5.7, 3.2), a B na B (8.9, 8.1). Niech punktem rozwiązania w (0, k) będzie C. Odbij A nad osią y, aby A 'było w (-5,7, 3,2). Odległość od A 'do C jest równa odległości od A do C. Dlatego problem można zredukować do punktu C tak, że A'C + CB jest zminimalizowane. Oczywiście byłby to punkt C, który leży na linii A'B.

Nie wiem, czy dobrze by to uogólniło do 3 lub więcej punktów.

C, 315 302 bajtów

t,i;double o,w,h,x,y,k,a,b,c;double g(N,S)double N,S[][2];{for(t=0;t<N;t++)k+=S[t][1];k/=N;for(i=0;i<9;i++){o=w=h=0;for(t=0;t<N;t++)x=S[t][0],y=S[t][1],a=y-k,c=k*k-2*k*y+x*x+y*y,o+=-a/sqrt(x*x+a*a),w+=x*x/pow(c,1.5),h+=3*x*x*a/pow(c,2.5);a=h/2;b=w-h*k;c=o-w*k+a*k*k;k=(-b+sqrt(b*b-4*a*c))/h;}return k;}

To nie jest wcale ładne i nie jest też krótkie. Pomyślałem, że skoro nie zamierzam wygrać konkursu długości, mogę spróbować wygrać (teoretyczną) konkurs dokładności! Kod jest prawdopodobnie rzędu wielkości dwa lub dwa razy szybszy niż rozwiązanie bruteforce i opiera się na matematycznej wygłupie.

Definiujemy funkcję, g(N,S)która przyjmuje jako dane wejściowe liczbę domów Noraz tablicę domów S[][2].

Tutaj jest rozwikłany, z przypadkiem testowym:

t,i;
double o,w,h,x,y,k,a,b,c;
double g(N,S)double N,S[][2];{
    /* Initially, let k hold the geometric mean of given y-values */
    for(t=0;t<N;t++)
        k+=S[t][1];
    k/=N;

    /* We approximate 9 times to ensure accuracy */
    for(i=0;i<9;i++){
        o=w=h=0;
        for(t=0;t<N;t++)
            /* Here, we are making running totals of partial derivatives */
            /* o is the first, w the second, and h the third*/
            x=S[t][0],
            y=S[t][1],
            a=y-k,
            c=k*k-2*k*y+x*x+y*y,
            o+=-a/sqrt(x*x+a*a),
            w+=x*x/pow(c,1.5),
            h+=3*x*x*a/pow(c,2.5);
        /* We now use these derivatives to find a (hopefully) closer k */
        a=h/2;
        b=w-h*k;
        c=o-w*k+a*k*k;
        k=(-b+sqrt(b*b-4*a*c))/h;
    }
    return k;
}
/* Our testing code */
int main(int argc, char** argv) {
    double test[2][2] = {
        {5.7, 3.2},
        {8.9, 8.1}
    };    
    printf("%.20lf\n", g(2, test));
    return 0;
}

Które wyjścia:

5.11301369863013732697

Ostrzeżenie: do pełnego zrozumienia może być wymagana znajomość rachunku różniczkowego!

Porozmawiajmy o matematyce.

Znamy odległość od pożądanego punktu (0, k)i domu i:

Tak więc całkowitą odległość Dod ndomów można zdefiniować w następujący sposób:

Chcielibyśmy zminimalizować tę funkcję, biorąc pochodną względem ki ustawiając ją na równą 0. Spróbujmy. Wiemy, że pochodne Dmożna opisać następująco:

Ale pierwsza częściowa pochodna każdego z nich Dijest całkiem zła ...

Niestety, nawet przy n == 2ustawieniu tych pochodnych 0i rozwiązywaniu problemu kstaje się bardzo katastrofalne. Potrzebujemy bardziej niezawodnej metody, nawet jeśli wymaga ona pewnego przybliżenia.

Wprowadź wielomiany Taylora.

Jeśli znamy wartość, D(k0)podobnie jak wszystkie Dpochodne w k0, możemy przepisać Djako seria Taylora:

Teraz ta formuła zawiera wiele rzeczy, a jej pochodne mogą być dość niewygodne, ale teraz mamy wielomianowe przybliżenie D !

Robiąc trochę rachunku różniczkowego, otrzymujemy dwa kolejne pochodne D, oceniając pochodne Di, tak jak wcześniej:

Skracając i oceniając pochodne, możemy teraz przybliżać Djako wielomian 3 stopnia postaci:

Gdzie A, B, C, Dsą po prostu liczby rzeczywiste.

Teraz to możemy zminimalizować. Kiedy weźmiemy pochodną i ustawimy ją na 0, otrzymamy równanie postaci:

Robiąc rachunek różniczkowy i podstawienia, wymyślamy te formuły dla a, b, and c:

Teraz nasz problem daje nam 2 rozwiązania podane w formule kwadratowej:

Cała formuła dla k byłaby ogromnym obciążeniem do napisania, więc robimy to w częściach tutaj i w kodzie.

Ponieważ wiemy, że wyższe kzawsze będą skutkować minimalną odległością w przybliżeniu D(mam na to naprawdę wspaniały dowód, którego margines w tym dokumencie nie jest w stanie pomieścić ...), nie musimy nawet brać pod uwagę mniejszej z rozwiązania.

Pozostaje jeszcze jeden problem. Dla celów dokładności konieczne jest, aby zacząć od k0tego, co najmniej na boisku, w którym oczekujemy odpowiedzi. W tym celu mój kod wybiera średnią geometryczną wartości y każdego domu.

Jako bezpieczne, powtarzamy cały problem ponownie 9 razy, zastępując k0go kprzy każdej iteracji, aby zapewnić dokładność.

Nie zrobiłem matematyki na temat tego, ile iteracji i ile pochodnych jest naprawdę potrzebnych, ale zdecydowałem się zachować ostrożność, dopóki nie potwierdzę dokładności.

Jeśli udało ci się to ze mną, bardzo dziękuję! Mam nadzieję, że zrozumiałeś, a jeśli zauważysz jakieś błędy (których prawdopodobnie jest wiele, jestem bardzo zmęczony), daj mi znać!

TI-BASIC, 20

fMin(sum(abs(iX-Ans)),X,~E99,E99

Pobiera dane na ekranie głównym kalkulatora serii TI-83 lub 84 w tej formie (możesz wpisać 2:pierwszy, który zostanie zignorowany):

{5.7+3.2i,8.9+8.1i}:[program name]

Jeśli domy są zawsze w odległości mniejszej niż miliard kilometrów od miejsca pochodzenia, E99 można zastąpić E9 dla rozmiaru 18 bajtów.

Gdyby istniał język golfa oparty na Mathematica, mógłby wygrać to wyzwanie w 10-14 bajtach.

Mathematica, 42 bajty

k/.Last@Minimize[Tr[Norm[#-{0,k}]&/@#],k]&

Jest to anonimowa funkcja, która pobiera listę par jako współrzędne domu i zwraca żądaną współrzędną y.

Jest to dość prosta implementacja. Mapujemy Norm[#-{0,k}]&na każdą współrzędną domu (która oblicza odległość do nieokreślonego punktu {0,k}na osi y) i sumujemy je wszystkie Tr[...](dla śledzenia, co jest równoważne z Totallistami 1-d). Następnie używamy wygody, Minimizeaby znaleźć minimum tej sumy w k. Daje to wynik formularza {distance, {k -> position}, więc musimy k/.Last@wyodrębnić to position, czego szukamy.

Pyth, 33 bajty

hosm.a,d,0NQcR^T3rhKSms*^T3ekQheK

Oto rozwiązanie brutalnej siły: porządkuje wszystkie możliwe lokalizacje restauracji, z rozdzielczością 0,001 km, według ich całkowitej odległości od domów, a następnie wybiera tę o najmniejszej całkowitej odległości. Lokalizacje domów przyjmuje jako listę 2 list wpisów pływaków na STDIN.

Demonstracja.

Rozdzielczość można ustawić w dowolnym miejscu od 1e-2 km do 1e-10 km przy tej samej długości kodu, ale z wykładniczym spowolnieniem w czasie wykonywania.

Wydaje mi się, że można jeszcze trochę zagrać w golfa, przyjrzę się temu później.

Python 2, 312

from math import*;A,L,p=[map(float,raw_input().split()) for i in range(input())],lambda a:a[1],0.001
def R(m,M,s):
 while m<=M:yield m;m+=s
m=min(A,key=L)[1];M=max(A,key=L)[1];r=(m+M)/2;s=r-m
while s>p:D={y:sum([sqrt(X*X+(Y-y)**2)for X,Y in A])for y in R(r-s,r+s,s*p)};r=min(D,key=D.get);s*=p;m=r-s;M=r+s
print r

R, 145 143 126

Podejrzewam, że zostało na to dużo miejsca do gry w golfa. Metoda prawie brutalna. Chciałbym znaleźć lepszy sposób na zrobienie tego. Myślałem, że Geometric Means może pomóc, ale niestety nie.

r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]

Testowe uruchomienie

> r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]
1: 5.7 3.2
3: 8.9 8.1
5: 
Read 4 items
[1] 5.113
> 

Zainteresowanych, jeśli są tylko dwa domy do rozważenia, zwróci akceptowalny wynik. Jednak spada na trzy. Nie mogę teraz iść dalej, ale pomyślałem, że niektóre mózgi tutaj mogą być w stanie coś z tym zrobić.

p=matrix(scan(),nr=2);weighted.mean(p[2,],sum(p[1,])-p[1,])

MATLAB, 42

Jeśli możesz przyjąć dane jako

I=[5.7 3.2
    8.9 8.1]

to stwierdzenie

fminunc(@(y)sum(hypot(I(:,1),I(:,2)-y)),0)

zwroty 5.113014445748538 .

Bezwstydnie kradnąc metodę Thomasa Kwa, możesz sprowadzić ją do co najmniej 30:

I=[5.7+3.2i 8.9+8.1i];
fminunc(@(y)sum(abs(I-i*y)),0)