Encuentre las coordenadas originales cuyas distancias de Manhattan se dan

Dadas las distancias de Manhattan de tres coordenadas en un plano 2-D, la tarea es encontrar las coordenadas originales. Imprime cualquier solución si son posibles varias soluciones; de lo contrario, imprime -1 .
 

Entrada: d1 = 3, d2 = 4, d3 = 5 
Salida: (0, 0), (3, 0) y (1, 3) 
La distancia de Manhattan entre (0, 0) y (3, 0) es 3, 
( 3, 0) a (1, 3) es 5 y (0, 0) a (1, 3) es 4
Entrada: d1 = 5, d2 = 10, d3 = 12 
Salida: -1 
 

Planteamiento: Analicemos cuando no existe solución. Primero, la desigualdad del triángulo debe cumplirse, es decir, la distancia más grande no debe exceder la suma de las otras dos. En segundo lugar, la suma de todas las distancias de Manhattan debe ser par. 
He aquí por qué, si tenemos tres puntos y sus coordenadas x son x1 , x2 y x3 tales que x1 < x2 < x3 . Contribuirán a la suma (x2 – x1) + (x3 – x1) + (x3 – x2) = 2 * (x3 – x1) . Se aplica la misma lógica para las coordenadas y. 
En todos los demás casos, tenemos una solución. Sean d1 , d2 y d3 las distancias Manhattan dadas. Fijar dos puntos como (0, 0) y(d1, 0) . Ahora que dos puntos son fijos, podemos encontrar fácilmente el tercer punto como x3 = (d1 + d2 – d3) / 2 y y3 = (d2 – x3) .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the original coordinated
void solve(int d1, int d2, int d3)
{
 
    // Maximum of the given distances
    int maxx = max(d1, max(d2, d3));
 
    // Sum of the given distances
    int sum = (d1 + d2 + d3);
 
    // Conditions when the
    // solution doesn't exist
    if (2 * maxx > sum or sum % 2 == 1) {
        cout << "-1";
        return;
    }
 
    // First coordinate
    int x1 = 0, y1 = 0;
 
    // Second coordinate
    int x2 = d1, y2 = 0;
 
    // Third coordinate
    int x3 = (d1 + d2 - d3) / 2;
    int y3 = (d2 + d3 - d1) / 2;
    cout << "(" << x1 << ", " << y1 << "), ("
         << x2 << ", " << y2 << ") and ("
         << x3 << ", " << y3 << ")";
}
 
// Driver code
int main()
{
    int d1 = 3, d2 = 4, d3 = 5;
    solve(d1, d2, d3);
 
    return 0;
}

// Java implementation of the approach
import java .io.*;
 
class GFG
{
     
// Function to find the original coordinated
static void solve(int d1, int d2, int d3)
{
 
    // Maximum of the given distances
    int maxx = Math.max(d1, Math.max(d2, d3));
 
    // Sum of the given distances
    int sum = (d1 + d2 + d3);
 
    // Conditions when the
    // solution doesn't exist
    if (2 * maxx > sum || sum % 2 == 1)
    {
        System.out.print("-1");
        return;
    }
 
    // First coordinate
    int x1 = 0, y1 = 0;
 
    // Second coordinate
    int x2 = d1, y2 = 0;
 
    // Third coordinate
    int x3 = (d1 + d2 - d3) / 2;
    int y3 = (d2 + d3 - d1) / 2;
    System.out.print("("+x1+", "+y1+"), ("+x2+", "+y2+") and ("+x3+", "+y3+")");
}
 
// Driver code
public static void main(String[] args)
{
    int d1 = 3, d2 = 4, d3 = 5;
    solve(d1, d2, d3);
 
}
}
 
// This code is contributed by anuj_67..

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to find the original coordinated
static void solve(int d1, int d2, int d3)
{
 
    // Maximum of the given distances
    int maxx = Math.Max(d1, Math.Max(d2, d3));
 
    // Sum of the given distances
    int sum = (d1 + d2 + d3);
 
    // Conditions when the
    // solution doesn't exist
    if (2 * maxx > sum || sum % 2 == 1)
    {
        Console.WriteLine("-1");
        return;
    }
 
    // First coordinate
    int x1 = 0, y1 = 0;
 
    // Second coordinate
    int x2 = d1, y2 = 0;
 
    // Third coordinate
    int x3 = (d1 + d2 - d3) / 2;
    int y3 = (d2 + d3 - d1) / 2;
    Console.WriteLine("("+x1+", "+y1+"), ("+x2+", "+y2+") and ("+x3+", "+y3+")");
}
 
// Driver code
static void Main()
{
    int d1 = 3, d2 = 4, d3 = 5;
    solve(d1, d2, d3);
 
}
}
 
// This code is contributed by mits

<script>
 
// Javascript implementation of the approach
 
// Function to find the original coordinated
function solve(d1, d2, d3)
{
 
    // Maximum of the given distances
    let maxx = Math.max(d1, Math.max(d2, d3));
 
    // Sum of the given distances
    let sum = (d1 + d2 + d3);
 
    // Conditions when the
    // solution doesn't exist
    if (2 * maxx > sum || sum % 2 == 1) {
        document.write("-1");
        return;
    }
 
    // First coordinate
    let x1 = 0, y1 = 0;
 
    // Second coordinate
    let x2 = d1, y2 = 0;
 
    // Third coordinate
    let x3 = parseInt((d1 + d2 - d3) / 2);
    let y3 = parseInt((d2 + d3 - d1) / 2);
    document.write("(" + x1 + ", " + y1 + "), ("
         + x2 + ", " + y2 + ") and ("
         + x3 + ", " + y3 + ")");
}
 
// Driver code
    let d1 = 3, d2 = 4, d3 = 5;
    solve(d1, d2, d3);
 
</script>

(0, 0), (3, 0) and (1, 3)

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)