Encuentra la coordenada que no pertenece a ningún cuadrado

Dada una array arr[] que consta de (4 * N + 1) pares de coordenadas que representan las coordenadas de las esquinas de cualquier N cuadrados de modo que solo una coordenada no pertenezca a ningún cuadrado, la tarea es encontrar esa coordenada que no No perteneces a ninguna plaza.

Ejemplos:

Entrada: N = 2, arr[] = { {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2} }
Salida: 1 1
Explicación:
El cuadrado tiene cuatro lados: x = 0, x = 2, y = 0, y = 2, ahora todos los puntos pertenecen al cuadrado excepto un punto (1, 1).

Entrada: N = 2, arr[] = { {0, 0}, {0, 1}, {0, 2}, {1, 0}, {0, 3}, {1, 2}, {2, 0}, {2, 1}, {2, 2} }
Salida: 0 3

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Las coordenadas de los lados del cuadrado aparecerán al menos dos veces porque N ≥ 2 . Por lo tanto, dado que solo hay un punto que no está en el límite, el máximo entre las coordenadas x que aparecen al menos dos veces nos dará la coordenada x del lado derecho del cuadrado.
• Los otros tres lados se pueden obtener de manera similar con diferentes combinaciones de coordenadas máximas/mínimas y x-/y.
• Después de conocer los lados del cuadrado, es fácil identificar el punto que no está en el límite.

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

• Iterar sobre un rango [0, N] usando la variable i y realizar los siguientes pasos:
  • Inicialice las variables x1, y1 con 2e9 y x2, y2 con -2e9 para almacenar los puntos del límite superior e inferior del cuadrado.
  • Iterar sobre un rango [0, N] usando la variable j y realizar los siguientes pasos:
    • Si i no es igual a j , realice los siguientes pasos:
      • Establezca x1 en el mínimo de x1 o p[j].primero .
      • Establezca x2 en el máximo de x2 o p[j].primero .
      • Establezca y1 en el mínimo de y1  o p[j].segundo .
      • Establezca y2 en el mínimo de y2 o p[j].segundo .
  • Inicialice una variable, diga ok a verdadero y las variables cnt1, cnt2, cnt3, cnt4 como 0 para almacenar el recuento de puntos con máximo y mínimo como x1, x2, y1, y2 .
  • Iterar sobre un rango [0, N] usando la variable j y realizar los siguientes pasos:
    • Si i no es igual a j , realice los siguientes pasos:
      • Si p[j].first es igual a x1, entonces, aumente el valor de cnt1 en 1 .
      • Si p[j].primero es igual a x2, entonces, aumente el valor de cnt2 en 1 .
      • Si p[j].segundo es igual a y1, entonces, aumente el valor de cnt3 en 1 .
      • Si p[j].segundo es igual a y2, entonces, aumente el valor de cnt4 en 1 .
    • De lo contrario, establezca el valor de ok en false .
  • Si el valor de ok es verdadero y los valores de cnt1, cnt2, cnt3, cnt4 son mayores que iguales a N, y x2 – x2 es igual a y2 – y1 , entonces, p[i] es el punto requerido. Imprime la respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define fi first
#define se second
 
// Function to find the point that is
// not a part of the side of a square
void findPoint(int n,
               vector<pair<int, int> > p)
{
    // Traverse each pair of coordinates
    for (int i = 0; i < n * 4 + 1; ++i) {
 
        int x1 = 2e9, x2 = -2e9;
        int y1 = 2e9, y2 = -2e9;
 
        for (int j = 0; j < n * 4 + 1; ++j)
            if (i != j) {
 
                // Minimize x-coordinate
                // in all the points
                // except current point
                x1 = min(x1, p[j].fi);
 
                // Maximize x-coordinate in
                // all the points except
                // the current point
                x2 = max(x2, p[j].fi);
 
                // Minimize y-coordinate
                // in all the points
                // except current point
                y1 = min(y1, p[j].se);
 
                // Maximize y-coordinate
                // in all the points
                // except current point
                y2 = max(y2, p[j].se);
            }
 
        bool ok = 1;
 
        int c1 = 0, c2 = 0;
        int c3 = 0, c4 = 0;
 
        for (int j = 1; j < n * 4 + 1; ++j)
            if (i != j) {
 
                // If x-coordinate matches
                // with other same line
                if ((p[j].fi == x1
                     || p[j].fi == x2)
                    || ((p[j].se == y1
                         || p[j].se == y2))) {
 
                    if (p[j].fi == x1)
                        ++c1;
 
                    if (p[j].fi == x2)
                        ++c2;
 
                    // If y coordinate matches
                    // with other same line
                    if (p[j].se == y1)
                        ++c3;
 
                    if (p[j].se == y2)
                        ++c4;
                }
                else
                    ok = 0;
            }
 
        // Check if the condition
        // for square exists or not
        if (ok && c1 >= n && c2 >= n
            && c3 >= n && c4 >= n
            && x2 - x1 == y2 - y1) {
 
            // Print the output
            cout << p[i].fi << " "
                 << p[i].se << "\n";
        }
    }
}
 
// Driver Code
int main()
{
    int N = 2;
    vector<pair<int, int> > arr
        = { { 0, 0 }, { 0, 1 }, { 0, 2 },
            { 1, 0 }, { 1, 1 }, { 1, 2 },
            { 2, 0 }, { 2, 1 }, { 2, 2 } };
 
    findPoint(N, arr);
 
    return 0;
}

import java.util.ArrayList;
 
//Java program for above approach
class GFG{
    static class pair<T, V>{
        T fi;
        V se;
        pair(T a, V b){
            this.fi = a;
            this.se = b;
        }
    }
 
    // Function to find the point that is
    // not a part of the side of a square
    static void findPoint(int n,
                   ArrayList<pair<Integer, Integer> > p)
    {
        // Traverse each pair of coordinates
        for (int i = 0; i < n * 4 + 1; ++i) {
 
            int x1 = (int) 2e9, x2 = (int) -2e9;
            int y1 = (int) 2e9, y2 = (int) -2e9;
 
            for (int j = 0; j < n * 4 + 1; ++j)
                if (i != j) {
 
                    // Minimize x-coordinate
                    // in all the points
                    // except current point
                    x1 = Math.min(x1, p.get(j).fi);
 
                    // Maximize x-coordinate in
                    // all the points except
                    // the current point
                    x2 = Math.max(x2, p.get(j).fi);
 
                    // Minimize y-coordinate
                    // in all the points
                    // except current point
                    y1 = Math.min(y1, p.get(j).se);
 
                    // Maximize y-coordinate
                    // in all the points
                    // except current point
                    y2 = Math.max(y2, p.get(j).se);
                }
 
            boolean ok = true;
 
            int c1 = 0, c2 = 0;
            int c3 = 0, c4 = 0;
 
            for (int j = 1; j < n * 4 + 1; ++j)
                if (i != j) {
 
                    // If x-coordinate matches
                    // with other same line
                    if ((p.get(j).fi == x1
                            || p.get(j).fi == x2)
                            || ((p.get(j).se == y1
                            || p.get(j).se == y2))) {
 
                        if (p.get(j).fi == x1)
                            ++c1;
 
                        if (p.get(j).fi == x2)
                            ++c2;
 
                        // If y coordinate matches
                        // with other same line
                        if (p.get(j).se == y1)
                            ++c3;
 
                        if (p.get(j).se == y2)
                            ++c4;
                    }
                    else
                        ok = false;
                }
 
            // Check if the condition
            // for square exists or not
            if (ok && c1 >= n && c2 >= n
                    && c3 >= n && c4 >= n
                    && x2 - x1 == y2 - y1) {
 
                // Print the output
                System.out.println(p.get(i).fi + " " + p.get(i).se);
 
            }
        }
    }
 
    //Driver Code
    public static void main(String[] args) {
        int N = 2;
        ArrayList<pair<Integer, Integer> > arr = new ArrayList<>();
        arr.add(new pair<Integer, Integer>(0,0));
        arr.add(new pair<Integer, Integer>(0,1));
        arr.add(new pair<Integer, Integer>(0,2));
        arr.add(new pair<Integer, Integer>(1,0));
        arr.add(new pair<Integer, Integer>(1,1));
        arr.add(new pair<Integer, Integer>(1,2));
        arr.add(new pair<Integer, Integer>(2,0));
        arr.add(new pair<Integer, Integer>(2,1));
        arr.add(new pair<Integer, Integer>(2,2));
        findPoint(N, arr);
 
    }
}
 
// This code is contributed by hritikrommie.

# Python 3 program for the above approach
 
# Function to find the point that is
# not a part of the side of a square
def findPoint(n, p):
    # Traverse each pair of coordinates
    for i in range(n * 4 + 1):
        x1 = 2e9
        x2 = -2e9
        y1 = 2e9
        y2 = -2e9
 
        for j in range(n * 4 + 1):
            if (i != j):
 
                # Minimize x-coordinate
                # in all the points
                # except current point
                x1 = min(x1, p[j][0])
 
                # Maximize x-coordinate in
                # all the points except
                # the current point
                x2 = max(x2, p[j][0])
 
                # Minimize y-coordinate
                # in all the points
                # except current point
                y1 = min(y1, p[j][1])
 
                # Maximize y-coordinate
                # in all the points
                # except current point
                y2 = max(y2, p[j][1])
 
        ok = 1
 
        c1 = 0
        c2 = 0
        c3 = 0
        c4 = 0
 
        for j in range(1,n * 4 + 1,1):
            if (i != j):
 
                # If x-coordinate matches
                # with other same line
                if ((p[j][0] == x1 or p[j][0] == x2) or (p[j][1] == y1 or p[j][1] == y2)):
                    if (p[j][0] == x1):
                        c1 += 1
 
                    if (p[j][0] == x2):
                        c2 += 1
 
                    # If y coordinate matches
                    # with other same line
                    if (p[j][1] == y1):
                        c3 += 1
 
                    if (p[j][1] == y2):
                        c4 += 1
                else:
                    ok = 0
 
        # Check if the condition
        # for square exists or not
        if (ok and c1 >= n and c2 >= n and c3 >= n and c4 >= n and x2 - x1 == y2 - y1):
 
            # Print the output
            print(p[i][0],p[i][1])
         
# Driver Code
if __name__ == '__main__':
    N = 2
    arr =  [[0, 0],[0, 1],[0, 2],[1, 0],[1, 1],[1, 2],[2, 0],[2, 1],[2, 2]]
 
    findPoint(N, arr)
     
    # This code is contributed by ipg2016107.

// JavaScript program for the above approach
 
// Function to find the point that is
// not a part of the side of a square
function findPoint(n, p)
{
    // Traverse each pair of coordinates
    for (let i = 0; i < n * 4 + 1; ++i) {
 
        let x1 = 2e9, x2 = -2e9;
        let y1 = 2e9, y2 = -2e9;
 
        for (let j = 0; j < n * 4 + 1; ++j){
            if (i != j) {
 
                // Minimize x-coordinate
                // in all the points
                // except current point
                x1 = Math.min(x1, p[j][0]);
 
                // Maximize x-coordinate in
                // all the points except
                // the current point
                x2 = Math.max(x2, p[j][0]);
 
                // Minimize y-coordinate
                // in all the points
                // except current point
                y1 = Math.min(y1, p[j][1]);
 
                // Maximize y-coordinate
                // in all the points
                // except current point
                y2 = Math.max(y2, p[j][1]);
            }
        }
 
        let ok = 1;
 
        let c1 = 0, c2 = 0;
        let c3 = 0, c4 = 0;
 
        for (let j = 1; j < n * 4 + 1; ++j){
            if (i != j) {
 
                // If x-coordinate matches
                // with other same line
                if ((p[j][0] == x1 || p[j][0] == x2) || (p[j][1] == y1 || p[j][1] == y2)) {
 
                    if (p[j][0] == x1)
                        ++c1;
 
                    if (p[j][0] == x2)
                        ++c2;
 
                    // If y coordinate matches
                    // with other same line
                    if (p[j][1] == y1)
                        ++c3;
 
                    if (p[j][1] == y2)
                        ++c4;
                }
                else{
                    ok = 0;   
                }
            } 
        }
 
        // Check if the condition
        // for square exists or not
        if (ok && c1 >= n && c2 >= n && c3 >= n && c4 >= n && x2 - x1 == y2 - y1) {
            // Print the output
            console.log(p[i][0] + " " + p[i][1]);
        }
    }
}
 
// Driver Code
 
let N = 2;
let arr =  [[0, 0], [0, 1], [0, 2],
        [1, 0], [1, 1], [1, 2 ],
        [2, 0], [2, 1], [2, 2]];
 
findPoint(N, arr);
 
// The code is contributed by Gautam goel(gautamgoel962)

1 1

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)