Hay n personas en un plano 2D. Usando distancias entre ellos vamos a encontrar sus posiciones. Para obtener una respuesta única, debe hacer cuatro suposiciones:

1. Hay al menos 3 personas.
2. La primera persona está en la posición (0, 0).
3. La segunda persona está en la posición (x, 0) para algunos x> 0.
4. La tercera persona está en la posición (x, y) para algunos y> 0.

Entonces, su desafío es escribir un programa o función que, dada una matriz 2D de distancias (donde se D[i][j]obtiene la distancia entre la persona iy j), devuelva una lista de sus coordenadas. Su respuesta debe tener una precisión de al menos 6 cifras significativas. La solución más corta en bytes gana.

Ejemplos

[[0.0, 3.0, 5.0], [3.0, 0.0, 4.0], [5.0, 4.0, 0.0]]

=>

[[0.0, 0.0], [3.0, 0.0], [3.0, 4.0]]


[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606,
0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704,
1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955],
[0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]

=>

[[0.0, 0.0], [0.0513, 0.0], [-0.39, 0.9836], [-0.5366, 0.0295], [-0.8094, -0.3221]]


[[0.0, 41.9519, 21.89390815, 108.37048253, 91.40006121, 49.35063671,
82.20983622, 83.69080223, 80.39436793, 86.5204431, 91.24484876, 22.32327813,
99.5351474, 72.1001264, 71.98278813, 99.8621559, 104.59071383, 108.61475753,
94.91576952, 93.20212636], [41.9519, 0.0, 24.33770482, 144.67214389,
132.28290899, 49.12079288, 85.34321428, 117.39095617, 103.60848008,
79.67795144, 69.52024038, 42.65007733, 105.60007249, 110.50120501,
89.92218111, 60.03623019, 133.61394005, 76.26668715, 130.54041305,
122.74547069], [21.89390815, 24.33770482, 0.0, 130.04213984, 112.98940283,
54.26427666, 71.35378232, 104.72088677, 81.67425703, 90.26668791,
71.13288376, 18.74250061, 109.87223765, 93.96339767, 69.46698314,
84.37362794, 124.38527485, 98.82541733, 116.43603102, 113.07526035],
[108.37048253, 144.67214389, 130.04213984, 0.0, 37.8990613, 111.2161525,
176.70411028, 28.99007398, 149.1355788, 124.17549005, 198.6298252,
126.02950495, 101.55746829, 37.24713176, 152.8114446, 189.29178553,
34.96711005, 180.83483984, 14.33728853, 35.75999058], [91.40006121,
132.28290899, 112.98940283, 37.8990613, 0.0, 111.05881157, 147.27385449,
44.12747289, 115.00173099, 134.19476383, 175.9860033, 104.1315771,
120.19673135, 27.75062658, 120.90347767, 184.88952087, 65.64187459,
183.20903265, 36.35677531, 60.34864715], [49.35063671, 49.12079288,
54.26427666, 111.2161525, 111.05881157, 0.0, 125.59451494, 82.23823276,
129.68328938, 37.23819968, 118.38443321, 68.15130552, 56.84347674,
84.29966837, 120.38742076, 78.30380948, 91.88522811, 72.15031414,
97.00421525, 82.23460459], [82.20983622, 85.34321428, 71.35378232,
176.70411028, 147.27385449, 125.59451494, 0.0, 158.1002588, 45.08950594,
161.43320938, 50.02998891, 59.93581537, 180.43028005, 139.95387244,
30.1390519, 133.42262669, 182.2085151, 158.47101132, 165.61965338,
170.96891788], [83.69080223, 117.39095617, 104.72088677, 28.99007398,
44.12747289, 82.23823276, 158.1002588, 0.0, 136.48099476, 96.57856065,
174.901291, 103.29640959, 77.53059476, 22.95598599, 137.23185588,
160.37639016, 26.14552185, 152.04872054, 14.96145727, 17.29636403],
[80.39436793, 103.60848008, 81.67425703, 149.1355788, 115.00173099,
129.68328938, 45.08950594, 136.48099476, 0.0, 166.89727482, 92.90019808,
63.53459104, 177.66159356, 115.1228903, 16.7609065, 160.79059188,
162.35278463, 179.82760993, 140.44928488, 151.9058635], [86.5204431,
79.67795144, 90.26668791, 124.17549005, 134.19476383, 37.23819968,
161.43320938, 96.57856065, 166.89727482, 0.0, 148.39351779, 105.1934756,
34.72852943, 106.44495924, 157.55442606, 83.19240274, 96.09890812,
61.77726814, 111.24915274, 89.68625779], [91.24484876, 69.52024038,
71.13288376, 198.6298252, 175.9860033, 118.38443321, 50.02998891,
174.901291, 92.90019808, 148.39351779, 0.0, 72.71434547, 175.07913091,
161.59035051, 76.3634308, 96.89392413, 195.433818, 127.21259331,
185.63246606, 184.09218079], [22.32327813, 42.65007733, 18.74250061,
126.02950495, 104.1315771, 68.15130552, 59.93581537, 103.29640959,
63.53459104, 105.1934756, 72.71434547, 0.0, 121.04924013, 88.90999601,
52.48935172, 102.51264644, 125.51831504, 117.54806623, 113.26375241,
114.12813777], [99.5351474, 105.60007249, 109.87223765, 101.55746829,
120.19673135, 56.84347674, 180.43028005, 77.53059476, 177.66159356,
34.72852943, 175.07913091, 121.04924013, 0.0, 93.63052717, 171.17130953,
117.77417844, 69.1477611, 95.81237385, 90.62801636, 65.7996984],
[72.1001264, 110.50120501, 93.96339767, 37.24713176, 27.75062658,
84.29966837, 139.95387244, 22.95598599, 115.1228903, 106.44495924,
161.59035051, 88.90999601, 93.63052717, 0.0, 117.17351252, 159.88686894,
48.89223072, 156.34374083, 25.76186961, 40.13509273], [71.98278813,
89.92218111, 69.46698314, 152.8114446, 120.90347767, 120.38742076,
30.1390519, 137.23185588, 16.7609065, 157.55442606, 76.3634308, 52.48935172,
171.17130953, 117.17351252, 0.0, 145.68608389, 162.51692098, 166.12926334,
142.8970605, 151.6440003], [99.8621559, 60.03623019, 84.37362794,
189.29178553, 184.88952087, 78.30380948, 133.42262669, 160.37639016,
160.79059188, 83.19240274, 96.89392413, 102.51264644, 117.77417844,
159.88686894, 145.68608389, 0.0, 169.4299171, 33.39882791, 175.00707479,
160.25054951], [104.59071383, 133.61394005, 124.38527485, 34.96711005,
65.64187459, 91.88522811, 182.2085151, 26.14552185, 162.35278463,
96.09890812, 195.433818, 125.51831504, 69.1477611, 48.89223072,
162.51692098, 169.4299171, 0.0, 156.08760216, 29.36259602, 11.39668734],
[108.61475753, 76.26668715, 98.82541733, 180.83483984, 183.20903265,
72.15031414, 158.47101132, 152.04872054, 179.82760993, 61.77726814,
127.21259331, 117.54806623, 95.81237385, 156.34374083, 166.12926334,
33.39882791, 156.08760216, 0.0, 167.00907734, 148.3962894], [94.91576952,
130.54041305, 116.43603102, 14.33728853, 36.35677531, 97.00421525,
165.61965338, 14.96145727, 140.44928488, 111.24915274, 185.63246606,
113.26375241, 90.62801636, 25.76186961, 142.8970605, 175.00707479,
29.36259602, 167.00907734, 0.0, 25.82164171], [93.20212636, 122.74547069,
113.07526035, 35.75999058, 60.34864715, 82.23460459, 170.96891788,
17.29636403, 151.9058635, 89.68625779, 184.09218079, 114.12813777,
65.7996984, 40.13509273, 151.6440003, 160.25054951, 11.39668734,
148.3962894, 25.82164171, 0.0]]

=>

[[0.0, 0.0], [41.9519, 0.0], [19.6294, 9.6969], [-88.505, -62.5382],
[-88.0155, -24.6423], [21.2457, -44.5433], [14.7187, 80.8815], [-59.789,
-58.5613], [-29.9331, 74.6141], [34.5297, -79.3315], [62.6017, 66.3826],
[5.2353, 21.7007], [6.1479, -99.3451], [-62.597, -35.7777], [-13.6408,
70.6785], [96.8736, -24.2478], [-61.4216, -84.6558], [92.2547, -57.3257],
[-74.7503, -58.4927], [-55.0613, -75.199]]

Python 2 , 183 178 166 161 160 159 158 156 bytes

Guardado 1 byte gracias a @Giuseppe y 2 bytes gracias a @JonathanFrech.

def f(D):
 X=D[0][1];o=[0,X];O=[0,0];n=2
 for d in D[2:]:y=d[0]**2;x=(y-d[1]**2)/X/2+X/2;y-=x*x;o+=x,;O+=y**.5*(y>d[2]**2-(x-o[2])**2or-1),;n+=1
 return o,O

Pruébalo en línea!

Utiliza los primeros 3 puntos para calcular el resto. Devuelve un par de x-coords, y-coords lo permitido en los comentarios .

R, 107

function(d){y=t(cmdscale(d))
y=y-y[,1]
p=cbind(c(y[3],-y[4]),y[4:3])%*%y/sum(y[,2]^2)^.5
p*c(1,sign(p[6]))}

La gran ventaja es en la línea 1, donde uso la función de R para el Escalado multidimensional (MDS). El resto es probablemente ineficiente (gracias por hacer sugerencias sobre cómo mejorar): la línea 2 traduce los datos para que el primer punto esté en (0, 0); la línea 3 gira los puntos para que el segundo punto esté en (0, x); la línea 4 voltea todo para que el tercer punto esté en y> 0.

R , 227 215 209 176 169 bytes

function(d){x=y=c(0,0)
x[2]=a=d[1,2]
d=d^2
i=3:nrow(d)
D=d[1,i]
x[i]=(D+a^2-d[2,i])/2/a
y[3]=e=sqrt(d[1,3]-x[3]^2)
y[i]=(D-d[3,i]+x[3]^2+e^2-2*x[3]*x[i])/2/e
Map(c,x,y)}

Pruébalo en línea!

Érase una vez, tomé un curso de Geometría Computacional. Me gustaría decir que ayudó, pero claramente no aprendí nada.

La entrada es una matriz R, con la salida una lista de vectores de 2 elementos (x,y)(que está más cerca de la especificación y ahorra bytes).

El problema aquí es, por supuesto, los primeros tres puntos. Una vez que arregle tres puntos, puede calcular todos los demás en función de ellos.

Simplemente utilicé un poco de álgebra para simplificar las cosas y luego noté que como solo estoy usando los primeros 3 puntos para resolver los demás, todo esto se vectorizó de manera muy clara.

Superado por flodel

Javascript (ES7), 202 193 bytes

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

Casos de prueba

let f =

d=>{for(k=7;(a=d.map((r,i)=>[x=(r[0]**2-r[1]**2+a*a)/2/a,(d[0][i]**2-x*x)**.5*(k>>i&1||-1)],a=d[0][1])).some(([x,y],i)=>a.some(([X,Y],j)=>(Math.hypot(x-X,y-Y)-d[i][j])**2>1e-6));k+=8);return a}

format = a => a.map(JSON.stringify).join`\n`

console.log(format(f([[0.0,3.0,5.0],[3.0,0.0,4.0],[5.0,4.0,0.0]])))
console.log(format(f([[0.0,0.0513,1.05809686,0.53741028,0.87113533],[0.0513,0.0,1.0780606,0.58863967,0.91899559],[1.05809686,1.0780606,0.0,0.96529704,1.37140397],[0.53741028,0.58863967,0.96529704,0.0,0.44501955],[0.87113533,0.91899559,1.37140397,0.44501955,0.0]])))
console.log(format(f([[0.0,41.9519,21.89390815,108.37048253,91.40006121,49.35063671,82.20983622,83.69080223,80.39436793,86.5204431,91.24484876,22.32327813,99.5351474,72.1001264,71.98278813,99.8621559,104.59071383,108.61475753,94.91576952,93.20212636],[41.9519,0.0,24.33770482,144.67214389,132.28290899,49.12079288,85.34321428,117.39095617,103.60848008,79.67795144,69.52024038,42.65007733,105.60007249,110.50120501,89.92218111,60.03623019,133.61394005,76.26668715,130.54041305,122.74547069],[21.89390815,24.33770482,0.0,130.04213984,112.98940283,54.26427666,71.35378232,104.72088677,81.67425703,90.26668791,71.13288376,18.74250061,109.87223765,93.96339767,69.46698314,84.37362794,124.38527485,98.82541733,116.43603102,113.07526035],[108.37048253,144.67214389,130.04213984,0.0,37.8990613,111.2161525,176.70411028,28.99007398,149.1355788,124.17549005,198.6298252,126.02950495,101.55746829,37.24713176,152.8114446,189.29178553,34.96711005,180.83483984,14.33728853,35.75999058],[91.40006121,132.28290899,112.98940283,37.8990613,0.0,111.05881157,147.27385449,44.12747289,115.00173099,134.19476383,175.9860033,104.1315771,120.19673135,27.75062658,120.90347767,184.88952087,65.64187459,183.20903265,36.35677531,60.34864715],[49.35063671,49.12079288,54.26427666,111.2161525,111.05881157,0.0,125.59451494,82.23823276,129.68328938,37.23819968,118.38443321,68.15130552,56.84347674,84.29966837,120.38742076,78.30380948,91.88522811,72.15031414,97.00421525,82.23460459],[82.20983622,85.34321428,71.35378232,176.70411028,147.27385449,125.59451494,0.0,158.1002588,45.08950594,161.43320938,50.02998891,59.93581537,180.43028005,139.95387244,30.1390519,133.42262669,182.2085151,158.47101132,165.61965338,170.96891788],[83.69080223,117.39095617,104.72088677,28.99007398,44.12747289,82.23823276,158.1002588,0.0,136.48099476,96.57856065,174.901291,103.29640959,77.53059476,22.95598599,137.23185588,160.37639016,26.14552185,152.04872054,14.96145727,17.29636403],[80.39436793,103.60848008,81.67425703,149.1355788,115.00173099,129.68328938,45.08950594,136.48099476,0.0,166.89727482,92.90019808,63.53459104,177.66159356,115.1228903,16.7609065,160.79059188,162.35278463,179.82760993,140.44928488,151.9058635],[86.5204431,79.67795144,90.26668791,124.17549005,134.19476383,37.23819968,161.43320938,96.57856065,166.89727482,0.0,148.39351779,105.1934756,34.72852943,106.44495924,157.55442606,83.19240274,96.09890812,61.77726814,111.24915274,89.68625779],[91.24484876,69.52024038,71.13288376,198.6298252,175.9860033,118.38443321,50.02998891,174.901291,92.90019808,148.39351779,0.0,72.71434547,175.07913091,161.59035051,76.3634308,96.89392413,195.433818,127.21259331,185.63246606,184.09218079],[22.32327813,42.65007733,18.74250061,126.02950495,104.1315771,68.15130552,59.93581537,103.29640959,63.53459104,105.1934756,72.71434547,0.0,121.04924013,88.90999601,52.48935172,102.51264644,125.51831504,117.54806623,113.26375241,114.12813777],[99.5351474,105.60007249,109.87223765,101.55746829,120.19673135,56.84347674,180.43028005,77.53059476,177.66159356,34.72852943,175.07913091,121.04924013,0.0,93.63052717,171.17130953,117.77417844,69.1477611,95.81237385,90.62801636,65.7996984],[72.1001264,110.50120501,93.96339767,37.24713176,27.75062658,84.29966837,139.95387244,22.95598599,115.1228903,106.44495924,161.59035051,88.90999601,93.63052717,0.0,117.17351252,159.88686894,48.89223072,156.34374083,25.76186961,40.13509273],[71.98278813,89.92218111,69.46698314,152.8114446,120.90347767,120.38742076,30.1390519,137.23185588,16.7609065,157.55442606,76.3634308,52.48935172,171.17130953,117.17351252,0.0,145.68608389,162.51692098,166.12926334,142.8970605,151.6440003],[99.8621559,60.03623019,84.37362794,189.29178553,184.88952087,78.30380948,133.42262669,160.37639016,160.79059188,83.19240274,96.89392413,102.51264644,117.77417844,159.88686894,145.68608389,0.0,169.4299171,33.39882791,175.00707479,160.25054951],[104.59071383,133.61394005,124.38527485,34.96711005,65.64187459,91.88522811,182.2085151,26.14552185,162.35278463,96.09890812,195.433818,125.51831504,69.1477611,48.89223072,162.51692098,169.4299171,0.0,156.08760216,29.36259602,11.39668734],[108.61475753,76.26668715,98.82541733,180.83483984,183.20903265,72.15031414,158.47101132,152.04872054,179.82760993,61.77726814,127.21259331,117.54806623,95.81237385,156.34374083,166.12926334,33.39882791,156.08760216,0.0,167.00907734,148.3962894],[94.91576952,130.54041305,116.43603102,14.33728853,36.35677531,97.00421525,165.61965338,14.96145727,140.44928488,111.24915274,185.63246606,113.26375241,90.62801636,25.76186961,142.8970605,175.00707479,29.36259602,167.00907734,0.0,25.82164171],[93.20212636,122.74547069,113.07526035,35.75999058,60.34864715,82.23460459,170.96891788,17.29636403,151.9058635,89.68625779,184.09218079,114.12813777,65.7996984,40.13509273,151.6440003,160.25054951,11.39668734,148.3962894,25.82164171,0.0]])))

¿Cómo?

Sea d _{i, j} la entrada y x _i , y _i la salida esperada.

Por las reglas del desafío, sabemos que:

• Para cualquier par (i, j) : d _{i, j} = √ ((x _i - x _j ) ² + (y _i - y _j ) ²)
• x ₀ = y ₀ = y ₁ = 0

Podemos deducir de inmediato que:

1. x ₁ = d _0,1

2. d _{0, j} = √ ((x ₀ - x _j ) ² + (y ₀ - y _j ) ²) = √ (x _j ² + y _j ²)
   d _{0, j} ² = x _j ² + y _j ²

3. d _{1, j} = √ ((x ₁ - x _j ) ² + (y ₁ - y _j ) ²) = √ ((x ₁ - x _j ) ² + y _j ²)
   d _{1, j} ² = (x ₁ - x _j ) ² + y _j ² = x ₁ ² + x _j ² + 2x ₁ x _j + y _j ² = d _0,1 ² + x _j ² + 2d _0,1 x _j + y _j ²

Computación x _j

Al usar 2 y 3, obtenemos:

x _j ² - (d _0,1 ² + x _j ² - 2d _0,1 x _j ) = d _{0, j} ² - d _{1, j} ²

Lo que lleva a:

x _j = (d _{0, j} ² - d _{1, j} ² + d _0,1 ²) / 2d _0,1

Computación y _j

Ahora que se conoce x _j , tenemos:

y _j ² = d _{0, j} ² - x _j ²

Lo que da:

y _j = ± √ (d _{0, j} ² - x _j ²)

Determinamos el signo de cada y _j simplemente probando todas las combinaciones posibles hasta que coincidamos con las distancias originales. También tenemos que asegurarnos de que tenemos y ₂ > 0 .

Hacemos eso usando la máscara de bits k donde los 1 se interpretan como positivos y los 0 se interpretan como negativos. Comenzamos con k = 7 ( 111 en binario) y agregamos 8 en cada iteración. De esta forma, se garantiza que los valores positivos de y _j se seleccionarán para 0 ≤ j ≤ 2 . (Podríamos comenzar con k = 4 igual de bien, porque y ₀ = y ₁ = 0 de todos modos. Pero usar 7 evita que aparezcan ceros negativos ).

JavaScript (ES7), 140 139 126 121 118 117 bytes

Guardado 1 byte gracias a @Giuseppe.

/* this line for testing only */ f =
D=>D.map((d,n)=>n>1?(y=d[0]**2,D[n]=x=(y-d[1]**2)/X/2+X/2,y-=x*x,[x,y**.5*(y>d[2]**2-(x-D[2])**2||-1)]):[X=n*d[0],0])

<!-- HTML for testing only --><textarea id="i" oninput="test()">[[0.0, 0.0513, 1.05809686, 0.53741028, 0.87113533], [0.0513, 0.0, 1.0780606, 0.58863967, 0.91899559], [1.05809686, 1.0780606, 0.0, 0.96529704, 1.37140397], [0.53741028, 0.58863967, 0.96529704, 0.0, 0.44501955], [0.87113533, 0.91899559, 1.37140397, 0.44501955, 0.0]]</textarea><pre id="o"></pre><script>window.onload=test=function(){try{document.querySelector("#o").innerHTML=JSON.stringify(f(JSON.parse(document.querySelector("#i").value)))}catch(e){}}</script>

Funciona algo así como mi respuesta de Python. Los [x,y]pares que regresaron resultaron mucho más cortos que las listas X e Y separadas en JS. Sobrescribe la lista de argumentos, así que no la use como entrada varias veces.

Mathematica, 160 bytes

(s=Table[0{,},n=Tr[1^#]];s[[2]]={#[[1,2]],0};f@i_:=RegionIntersection~Fold~Table[s[[j]]~Circle~#[[j,i]],{j,i-1}];s[[3]]=Last@@f@3;Do[s[[i]]=#&@@f@i,{i,4,n}];s)&

El programa utiliza la función integrada RegionIntersectionpara calcular el punto de intersección de los círculos. El programa requiere coordenadas exactas para funcionar.

Esto supone RegionIntersectionque el punto con la coordenada y más alta sea el último en su resultado si la coordenada x es igual. (al menos es cierto en Wolfram Sandbox)

Por alguna razón RegionIntersectionno funciona si hay demasiados círculos en su entrada, así que tengo que procesar cada par una vez usando Fold.

Demostrar captura de pantalla: