Você é o dono de um restaurante. Você está abrindo em uma nova área em Cartesia, onde há apenas uma estrada principal, conhecida como eixo y. Você deseja colocar seu restaurante de modo a minimizar a distância total do restaurante e de cada uma das casas nessa área.

Entrada :

A entrada será

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

onde cada casa é uma coordenada no formulário x y. Cada unidade representa um quilômetro.

Você pode receber a entrada como uma string ou fornecer uma função que aceita a entrada, em qualquer formato que você escolher, como seus argumentos.

Saída : a coordenada y do seu restaurante (lembre-se, ele estará localizado no eixo y). Na verdade, ele estará localizado ao lado da estrada, mas a diferença é insignificante.

Essencialmente, se a enésima casa é h_ne Dé a função de distância, você deseja encontrar kuma que D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k))seja minimizada.

Observe que a distância é calculada como se o cliente viajasse em uma linha exatamente reta da casa até o restaurante. Essa é a distância do (x, y)seu restaurante sqrt(x^2 + (y - k)^2).

A saída deve ser precisa com pelo menos 2 casas decimais.

A saída pode ser impressa como uma sequência ou pode ser retornada da função.

Exemplo de entrada / saída:

Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

A distância total neste exemplo é de cerca de 15.4003quilômetros.

Este é o código golf - o código mais curto vence.

PS: Também estou interessado em uma solução matemática que não é apenas força bruta. Não ganhará o código de golfe, mas receberá alguns votos positivos. Aqui está como eu fiz o problema de exemplo:

Seja o ponto A localizado em A (5,7, 3,2) e B em B (8,9, 8,1). Deixe o ponto de solução em (0, k) ser C. Reflita A sobre o eixo y para fazer A 'em (-5,7, 3,2). A distância de A 'a C é igual à distância de A a C. Portanto, o problema pode ser reduzido ao ponto C de modo que A'C + CB seja minimizado. Obviamente, este seria o ponto C que está na linha A'B.

Não sei se isso generalizaria bem para 3 ou mais pontos.

C, 315 302 bytes

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

Isso está longe de ser bonito e também não é curto. Imaginei que, como não vou ganhar o concurso de duração, posso tentar vencer o concurso de precisão (teórico)! O código é provavelmente uma ordem de magnitude ou duas mais rápida que a solução bruteforce e depende de um pouco de tolice matemática.

Definimos uma função g(N,S)que recebe como entrada o número de casas N, e uma matriz de casas S[][2].

Aqui está desvendado, com um caso de teste:

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

Quais saídas:

5.11301369863013732697

Aviso: O conhecimento de alguns cálculos pode ser necessário para um entendimento completo!

Então, vamos falar sobre a matemática.

Sabemos a distância do nosso ponto desejado (0, k)e uma casai :

E assim a distância total Dden casas pode ser definida da seguinte maneira:

O que gostaríamos de fazer é minimizar essa função pegando uma derivada em relação a ke configurando-a igual a 0. Vamos tentar. Sabemos que os derivados de Dpodem ser descritos da seguinte forma:

Mas a primeira derivada parcial de cada uma Dié muito ruim ...

Infelizmente, mesmo assim n == 2, definir esses derivativos 0e resolver isso kse torna desastroso muito rapidamente. Precisamos de um método mais robusto, mesmo que exija alguma aproximação.

Digite polinômios de Taylor.

Se conhecermos o valor D(k0)e todos Dos derivativos de k0, podemos reescrever Dcomo uma série de Taylor:

Agora, esta fórmula tem um monte de coisas e seus derivados podem ficar bem difíceis de manejar, mas agora temos uma aproximação polinomial de D !

Fazendo um pouco de cálculo, encontramos as próximas duas derivadas de D, avaliando as derivadas de Di, exatamente como antes:

Ao truncar e avaliar as derivadas, podemos agora aproximar-nos Dcomo um polinômio de terceiro grau da forma:

Onde A, B, C, D são simplesmente números reais.

Agora isso podemos minimizar. Quando pegamos uma derivada e a definimos como 0, terminaremos com uma equação da forma:

Fazendo o cálculo e as substituições, criamos estas fórmulas para a, b, and c:

Agora, nosso problema nos dá 2 soluções dadas pela fórmula quadrática:

Toda a fórmula para k seria um fardo enorme para escrever, por isso fazemos em partes aqui e no código.

Como sabemos que quanto maior k sempre resultará na distância mínima da nossa aproximação D(eu tenho uma prova realmente maravilhosa disso, que a margem deste artigo é insuficiente para conter ...), nem precisamos considerar o menor as soluções.

Um problema final permanece. Para fins de precisão, é necessário começar com umk0 que seja pelo menos no estádio em que esperamos que a resposta esteja. Para esse propósito, meu código escolhe a média geométrica dos valores y de cada casa.

Como à prova de falhas, repetimos o problema inteiro novamente 9 vezes, substituindo k0pork a cada iteração, para garantir a precisão.

Eu não fiz as contas sobre quantas iterações e quantas derivadas são realmente necessárias, mas optei por errar por precaução até poder confirmar a precisão.

Se você passou por isso comigo, muito obrigado! Espero que você entenda e, se detectar algum erro (dos quais provavelmente há muitos, estou muito cansado), entre em contato!

TI-BASIC, 20

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

Recebe entrada na tela inicial da calculadora da série TI-83 ou 84 neste formulário (você pode digitar um 2:primeiro, o que seria ignorado):

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

Se as casas estiverem sempre a menos de um bilhão de quilômetros da origem, o E99 poderá ser substituído pelo E9 por um tamanho de 18 bytes.

Se houvesse uma linguagem de golfe baseada no Mathematica, ela poderia vencer esse desafio em 10 a 14 bytes.

Mathematica, 42 bytes

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

Esta é uma função anônima que pega uma lista de pares conforme a casa coordena e retorna a coordenada y desejada.

É uma implementação bastante direta. Mapeamos Norm[#-{0,k}]&para cada coordenada da casa (que calcula a distância até um ponto indeterminado {0,k}no eixo y) e somamos todas elas Tr[...](para traçar, o que equivale a Totallistas 1-d). Em seguida, usamos o conveniente Minimizepara encontrar o mínimo dessa soma em k. Isso fornece um resultado do formulário {distance, {k -> position}, portanto, precisamos k/.Last@extrair o positionque estamos procurando.

Pitão, 33 bytes

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

Esta é a solução da força bruta: ela ordena todos os locais possíveis do restaurante, com uma resolução de 0,001 km, pela distância total das casas e, em seguida, seleciona aquele com a menor distância total. Leva os locais da casa como uma lista de 2 listas de carros alegóricos no STDIN.

Demonstração.

A resolução pode ser definida entre 1e-2 km e 1e-10 km no mesmo comprimento de código, mas com lentidão exponencial no tempo de execução.

Eu sinto que isso poderia ser jogado um pouco mais, vou olhar novamente mais tarde.

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

Muita sala de golfe sobrou nisto, suspeito. Praticamente um método de força bruta. Eu gostaria de encontrar uma maneira melhor de fazer isso. Eu acho que o Geometric Means pode ajudar, mas infelizmente não.

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

Execução de teste

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

Por uma questão de interesse, se houver apenas duas casas a considerar, o seguinte retornará um resultado aceitável. No entanto, cai em três. Não posso ir mais longe no momento, mas pensei que alguns dos cérebros aqui pudessem fazer algo com isso.

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

MATLAB, 42

Se não for aceitável receber a entrada como

I=[5.7 3.2
    8.9 8.1]

então esta afirmação

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

retorna 5.113014445748538 .

Roubando descaradamente o método de Thomas Kwa, você pode reduzi-lo a 30 pelo menos:

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