Encuentre 4 puntos con la misma distancia de Manhattan entre cualquier par

Dado un número entero N , encuentre 4 puntos en un plano 2D que tenga coordenadas integrales, de modo que la distancia de Manhattan entre cualquier par de puntos sea igual a N .

Ejemplos:

Entrada: N = 6
Salida: { {0, -3}, {3, 0}, {-3, 0}, {0, 3} }
Explicación: se puede calcular fácilmente que la distancia de Manhattan entre todos los pares posibles es 6 .

Entrada: N = 11
Salida: -1
Explicación: No es posible ubicar 4 puntos tales que la distancia de Manhattan entre todos los pares sea 11

Planteamiento: La idea para resolver el problema se basa en la siguiente observación:

Los cuadrados que tienen los 4 vértices en los 4 ejes de coordenadas (1 vértice en cada eje) equidistantes del origen tienen la misma distancia entre cualquier par de vértices, que es el doble de la distancia entre cualquier vértice y el origen.
Si N es impar, no se puede dividir en 2 partes enteras iguales. Por lo tanto, no se puede formar un cuadrado tal que los vértices opuestos estén a la misma distancia del origen (es decir, N/2), siendo la distancia entre ellos N, en cuyo caso no se pueden encontrar 4 puntos que satisfagan la condición dada.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Comprueba si N es par o impar.
• Si N es impar entonces esos 4 puntos no se pueden encontrar.
• De lo contrario, establezca los cuatro puntos como {N/2, 0}, {-N/2, 0}, {0, N/2}, {0, -N/2}

A continuación se muestra la implementación del enfoque anterior.

// C++ code for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find 4 points such that
// manhattan distance between
// any two of them is equal
vector<pair<int, int> > findPoints(int N)
{
    // Initializing vector of pairs to
    // store the 4 pairs
    vector<pair<int, int> > points;
 
    // If N is odd, it is impossible
    // to find 4 such points
    if (N % 2 == 1)
        return points;
 
    // Initializing a variable
    // with value equal to N/2
    int point = N / 2;
 
    // Pushing all the 4 pairs into
    // vector "points" such that distance
    // between any two is equal
    points.push_back({ 0, point });
    points.push_back({ 0, -point });
    points.push_back({ point, 0 });
    points.push_back({ -point, 0 });
 
    // Returning "points" vector
    return points;
}
 
// Function to print
void print(int N)
{
    vector<pair<int, int> > ans
        = findPoints(N);
    if (ans.size() == 0)
        cout << -1;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << ", "
             << ans[i].second << "\n";
    }
}
 
// Driver Code
int main()
{
    int N = 6;
 
    // Calling the print function
    print(N);
    return 0;
}

// Java code for above approach
import java.io.*;
 
class GFG {
 
  // Function to find 4 points such that
  // manhattan distance between
  // any two of them is equal
  static int[][] findPoints(int N)
  {
 
    // Initializing vector of pairs to
    // store the 4 pairs
    int[][]points=new int[4][2];
 
    // If N is odd, it is impossible
    // to find 4 such points
    if (N % 2 == 1)
      return points;
 
    // Initializing a variable
    // with value equal to N/2
    int point = N / 2;
 
    // Pushing all the 4 pairs into
    // vector "points" such that distance
    // between any two is equal
    points[0][0] = 0;
    points[0][ 1] = point;
    points[1][0] = 0;
    points[1][1] = -point;
    points[2][0] = point;
    points[2][1] = 0;
    points[3][0] = -point;
    points[3][1] = 0;
 
    // Returning "points" vector
    return points;
  }
 
  // Function to print
  static void print(int N)
  {
    int[][] ans = findPoints(N);
    if (ans.length == 0)
      System.out.print(-1);
    for (int i = 0; i < ans.length; i++) {
      System.out.println(ans[i][0] + ", " + ans[i][1]);
    }
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 6;
 
    // Calling the print function
    print(N);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code for the above approach
 
# Function to find 4 points such that
# manhattan distance between
# any two of them is equal
def findPoints(N):
   
    # Initializing vector of pairs to
    # store the 4 pairs
    points = []
 
    # If N is odd, it is impossible
    # to find 4 such points
    if (N % 2 == 1):
        return points
 
    # Initializing a variable
    # with value equal to N/2
    point = (N // 2)
 
    # Pushing all the 4 pairs into
    # vector "points" such that distance
    # between any two is equal
    points.append([0,point ])
    points.append([0,-1 * point ])
    points.append([point,0 ])
    points.append([-1 * point,0 ])
 
    # Returning "points" vector
    return points
 
# Function to print
def Print(N):
    ans = findPoints(N)
    if (len(ans) == 0):
        print(-1)
    for i in range(len(ans)):
        print(str(ans[i][0]) + ", " + str(ans[i][1]))
 
# Driver Code
N = 6
 
# Calling the print function
Print(N)
 
# This code is contributed by shinjanpatra

// C# code for above approach
using System;
class GFG {
 
    // Function to find 4 points such that
    // manhattan distance between
    // any two of them is equal
    static int[, ] findPoints(int N)
    {
       
        // Initializing vector of pairs to
        // store the 4 pairs
        int[, ] points = new int[4, 2];
 
        // If N is odd, it is impossible
        // to find 4 such points
        if (N % 2 == 1)
            return points;
 
        // Initializing a variable
        // with value equal to N/2
        int point = N / 2;
 
        // Pushing all the 4 pairs into
        // vector "points" such that distance
        // between any two is equal
        points[0, 0] = 0;
        points[0, 1] = point;
        points[1, 0] = 0;
        points[1, 1] = -point;
        points[2, 0] = point;
        points[2, 1] = 0;
        points[3, 0] = -point;
        points[3, 1] = 0;
 
        // Returning "points" vector
        return points;
    }
 
    // Function to print
    static void print(int N)
    {
        int[, ] ans = findPoints(N);
        if (ans.GetLength(0) == 0)
            Console.Write(-1);
        for (int i = 0; i < ans.GetLength(0); i++) {
            Console.WriteLine(ans[i, 0] + ", " + ans[i, 1]);
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 6;
 
        // Calling the print function
        print(N);
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code for the above approach
 
    // Function to find 4 points such that
    // manhattan distance between
    // any two of them is equal
    function findPoints(N) {
        // Initializing vector of pairs to
        // store the 4 pairs
        let points = [];
 
        // If N is odd, it is impossible
        // to find 4 such points
        if (N % 2 == 1)
            return points;
 
        // Initializing a variable
        // with value equal to N/2
        let point = Math.floor(N / 2);
 
        // Pushing all the 4 pairs into
        // vector "points" such that distance
        // between any two is equal
        points.push({ first: 0, second: point });
        points.push({ first: 0, second: -1 * point });
        points.push({ first: point, second: 0 });
        points.push({ first: -1 * point, second: 0 });
 
        // Returning "points" vector
        return points;
    }
 
    // Function to print
    function print(N) {
        let ans = findPoints(N);
        if (ans.length == 0)
            document.write(-1);
        for (let i = 0; i < ans.length; i++) {
            document.write(ans[i].first + ", "
                + ans[i].second + '<br>');
        }
    }
 
    // Driver Code
    let N = 6;
 
    // Calling the print function
    print(N);
 
    // This code is contributed by Potta Lokesh
</script>

0, 3
0, -3
3, 0
-3, 0

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)