Encuentre los puntos enteros (x, y) con la distancia de Manhattan al menos N

Dado un número N, la tarea es encontrar los puntos enteros (x, y) tales que 0 <= x, y <= N y la distancia de Manhattan entre dos puntos cualquiera sea al menos N.
Ejemplos: 
 

Input: N = 3
Output: (0, 0) (0, 3) (3, 0) (3, 3)

Input: N = 4
Output: (0, 0) (0, 4) (4, 0) (4, 4) (2, 2)

Acercarse: 
 

• Manhattan La distancia entre dos puntos (x ₁ , y ₁ ) y (x ₂ , y ₂ ) es: 
  |x ₁ – x ₂ | + |y ₁ – y ₂ |
• Aquí, para todos los pares de puntos, esta distancia será al menos N.
• Como 0 <= x <= N y 0 <= y <= N , podemos imaginar un cuadrado de lado N cuya esquina inferior izquierda es (0, 0) y la esquina superior derecha es (N, N).
• Entonces, si colocamos 4 puntos en esta esquina, la distancia de Manhattan será al menos N.
• Ahora que tenemos que maximizar el número del punto, tenemos que verificar si hay algún punto disponible dentro del cuadrado.
• Si N es par, entonces el punto medio del cuadrado que es (N/2, N/2) es un punto entero; de lo contrario, será un valor flotante ya que N/2 no es un número entero cuando N es impar.
• Entonces, la única posición disponible es el punto medio y podemos poner un punto allí solo si N es par.
• Entonces, el número de puntos será 4 si N es impar y si N es par, entonces el número de puntos será 5.

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

// C++ code to Find the integer points (x, y)
// with Manhattan distance atleast N
 
#include <bits/stdc++.h>
using namespace std;
 
// C++ function to find all possible point
vector<pair<int, int> > FindPoints(int n)
{
 
    vector<pair<int, int> > v;
 
    // Find all 4 corners of the square
    // whose side length is n
    v.push_back({ 0, 0 });
    v.push_back({ 0, n });
    v.push_back({ n, 0 });
    v.push_back({ n, n });
 
    // If n is even then the middle point
    // of the square will be an integer,
    // so we will take that point
    if (n % 2 == 0)
        v.push_back({ n / 2, n / 2 });
 
    return v;
}
 
// Driver Code
int main()
{
 
    int N = 8;
 
    vector<pair<int, int> > v
        = FindPoints(N);
 
    // Printing all possible points
    for (auto i : v) {
        cout << "(" << i.first << ", "
             << i.second << ") ";
    }
    return 0;
}

// Java code to Find the integer points (x, y)
// with Manhattan distance atleast N
import java.util.*;
 
class GFG
{
 
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Java function to find all possible point
static Vector<pair> FindPoints(int n)
{
    Vector<pair> v = new Vector<pair>();
 
    // Find all 4 corners of the square
    // whose side length is n
    v.add(new pair( 0, 0 ));
    v.add(new pair( 0, n ));
    v.add(new pair( n, 0 ));
    v.add(new pair( n, n ));
 
    // If n is even then the middle point
    // of the square will be an integer,
    // so we will take that point
    if (n % 2 == 0)
        v.add(new pair( n / 2, n / 2 ));
 
    return v;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 8;
 
    Vector<pair > v = FindPoints(N);
 
    // Printing all possible points
    for (pair i : v)
    {
        System.out.print("(" + i.first + ", " +
                               i.second + ") ");
    }
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 code to Find the integer points (x, y)
# with Manhattan distance atleast N
 
# function to find all possible point
def FindPoints(n) :
 
    v = [];
 
    # Find all 4 corners of the square
    # whose side length is n
    v.append([ 0, 0 ]);
    v.append([ 0, n ]);
    v.append([ n, 0 ]);
    v.append([ n, n ]);
 
    # If n is even then the middle point
    # of the square will be an integer,
    # so we will take that point
    if (n % 2 == 0) :
        v.append([ n // 2, n // 2 ]);
 
    return v;
 
# Driver Code
if __name__ == "__main__" :
 
    N = 8;
 
    v = FindPoints(N);
 
    # Printing all possible points
    for element in v :
        print("(", element[0],
              ",", element[1], ")", end = " ");
 
# This code is contributed by AnkitRai01

// C# code to Find the integer points (x, y)
// with Manhattan distance atleast N
using System;
using System.Collections.Generic;
 
class GFG
{
 
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to find all possible point
static List<pair> FindPoints(int n)
{
    List<pair> v = new List<pair>();
 
    // Find all 4 corners of the square
    // whose side length is n
    v.Add(new pair( 0, 0 ));
    v.Add(new pair( 0, n ));
    v.Add(new pair( n, 0 ));
    v.Add(new pair( n, n ));
 
    // If n is even then the middle point
    // of the square will be an integer,
    // so we will take that point
    if (n % 2 == 0)
        v.Add(new pair( n / 2, n / 2 ));
 
    return v;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 8;
 
    List<pair > v = FindPoints(N);
 
    // Printing all possible points
    foreach (pair i in v)
    {
        Console.Write("(" + i.first + ", " +
                            i.second + ") ");
    }
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript code to Find the integer points (x, y)
// with Manhattan distance atleast N
 
// C++ function to find all possible point
function FindPoints(n)
{
 
    var v = [];
 
    // Find all 4 corners of the square
    // whose side length is n
    v.push([ 0, 0 ]);
    v.push([ 0, n ]);
    v.push([ n, 0 ]);
    v.push([ n, n ]);
 
    // If n is even then the middle point
    // of the square will be an integer,
    // so we will take that point
    if (n % 2 == 0)
        v.push([ n / 2, n / 2 ]);
 
    return v;
}
 
// Driver Code
var N = 8;
var v = FindPoints(N);
// Printing all possible points
v.forEach(i => {
    document.write( "(" + i[0] + ", "
         + i[1] + ") ");
});
 
// This code is contributed by rrrtnx.
</script>

(0, 0) (0, 8) (8, 0) (8, 8) (4, 4)

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)