Vértice faltante entre N rectángulos paralelos al eje

Dados N rectángulos paralelos al eje en un sistema de coordenadas cartesianas 2-D y coordenadas de vértices 4N-1 , la tarea es encontrar el único vértice que falta. Ejemplos: 
 

Entrada: N = 2, V[][] = {{1, 1}, {1, 2}, {4, 6}, {2, 1}, {9, 6}, {9, 3}, { 4, 3} 
Salida: {2, 2} 
Explicación: 
Las coordenadas que forman un rectángulo paralelo al eje son {4, 6}, {9, 6}, {4, 3}, {9, 3}. 
Para que las coordenadas restantes formen un rectángulo {1, 1}, {1, 2}, {2, 1}, la coordenada que falta es {2, 2}
Entrada: N = 3, V[][] = {{3 , 8}, {0, 0}, {4, 6}, {0, 2}, {9, 6}, {9, 3}, {4, 3}, {6, 4}, {1, 0 }, {3, 4}, {6, 8}} 
Salida: {1, 2}

Enfoque: 
siga los pasos a continuación para resolver el problema:

• Almacene las coordenadas x y las coordenadas y de las frecuencias en un mapa .
• Iterar sobre el Mapa para encontrar un elemento con frecuencia impar para ambas coordenadas.
• Finalmente, imprima las coordenadas x e y con frecuencia impar.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
void MissingPoint(vector<pair<int, int> > V,
                  int N)
{
    map<int, int> mp;
    for (int i = 0; i < V.size(); i++) {
        mp[V[i].first]++;
    }
 
    int x, y;
    for (auto it : mp) {
        if (it.second % 2 == 1) {
            x = it.first;
            break;
        }
    }
    mp.clear();
    for (int i = 0; i < V.size(); i++) {
        mp[V[i].second]++;
    }
 
    for (auto it : mp) {
        if (it.second % 2 == 1) {
            y = it.first;
            break;
        }
    }
 
    cout << x << " " << y;
}
 
// Driver Code
int main()
{
 
    // Number of rectangles
    int N = 2;
 
    // Stores the coordinates
    vector<pair<int, int> > V;
 
    // Insert the coordinates
    V.push_back({ 1, 1 });
    V.push_back({ 1, 2 });
    V.push_back({ 4, 6 });
    V.push_back({ 2, 1 });
    V.push_back({ 9, 6 });
    V.push_back({ 9, 3 });
    V.push_back({ 4, 3 });
 
    MissingPoint(V, N);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
    static class pair
    {
        int first, second;
        public pair(int first, int second) 
        {
            this.first = first;
            this.second = second;
        }   
    }
static void MissingPoint(Vector<pair> V, int N)
{
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
    for (int i = 0; i < V.size(); i++)
    {
        if(mp.containsKey(V.get(i).first))
            mp.put(V.get(i).first,
                   V.get(i).first + 1);
        else
            mp.put(V.get(i).first, 1);
    }
    int x = 0, y = 0;
    for (Map.Entry<Integer,
                   Integer> it : mp.entrySet())
    {
        if (it.getValue() % 2 == 1)
        {
            x = it.getKey();
            break;
        }
    }
    mp.clear();
    for (int i = 0; i < V.size(); i++)
    {
        if(mp.containsKey(V.get(i).second))
            mp.put(V.get(i).second,
                   V.get(i).second + 1);
        else
            mp.put(V.get(i).second, 1);
    }
    for (Map.Entry<Integer,
                   Integer> it : mp.entrySet())
    {
        if (it.getValue() % 2 == 1)
        {
            y = it.getKey();
            break;
        }
    }
    System.out.print(x + " " + y);
}
 
// Driver Code
public static void main(String[] args)
{
    // Number of rectangles
    int N = 2;
 
    // Stores the coordinates
    Vector<pair> V = new Vector<pair>();
 
    // Insert the coordinates
    V.add(new pair(1, 1));
    V.add(new pair(1, 2));
    V.add(new pair(4, 6));
    V.add(new pair(2, 1));
    V.add(new pair(9, 6));
    V.add(new pair(9, 3));
    V.add(new pair(4, 3));
 
    MissingPoint(V, N);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
from collections import defaultdict
 
def MissingPoint(V, N):
 
    mp = defaultdict(lambda : 0)
    for i in range(len(V)):
        mp[V[i][0]] += 1
 
    for it in mp.keys():
        if(mp[it] % 2 == 1):
            x = it
            break
 
    del mp
    mp = defaultdict(lambda : 0)
 
    for i in range(len(V)):
        mp[V[i][1]] += 1
 
    for it in mp.keys():
        if(mp[it] % 2 == 1):
            y = it
            break
 
    print(x, y)
 
# Driver code
if __name__ == '__main__':
 
    # Number of rectangles
    N = 2
 
    # Stores the coordinates
    V = []
 
    # Insert the coordinates
    V.append([1, 1])
    V.append([1, 2])
    V.append([4, 6])
    V.append([2, 1])
    V.append([9, 6])
    V.append([9, 3])
    V.append([4, 3])
 
    MissingPoint(V, N)
 
# This code is contributed by Shivam Singh

// C# Program to implement
// the above approach
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;
  }   
}
   
static void MissingPoint(List<pair> V,
                         int N)
{
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
  for (int i = 0; i < V.Count; i++)
  {
    if(mp.ContainsKey(V[i].first))
      mp[V[i].first] = mp[V[i].first] + 1;
    else
      mp.Add(V[i].first, 1);
  }
   
  int x = 0, y = 0;
  foreach (KeyValuePair<int,
                        int> it in mp)
  {
    if (it.Value % 2 == 1)
    {
      x = it.Key;
      break;
    }
  }
  mp.Clear();
   
  for (int i = 0; i < V.Count; i++)
  {
    if(mp.ContainsKey(V[i].second))
      mp[V[i].second] = mp[V[i].second] + 1;
    else
      mp.Add(V[i].second, 1);
  }
   
  foreach (KeyValuePair<int,
                        int> it in mp)
  {
    if (it.Value % 2 == 1)
    {
      y = it.Key;
      break;
    }
  }
  Console.Write(x + " " + y);
}
 
// Driver Code
public static void Main(String[] args)
{
  // Number of rectangles
  int N = 2;
 
  // Stores the coordinates
  List<pair> V = new List<pair>();
 
  // Insert the coordinates
  V.Add(new pair(1, 1));
  V.Add(new pair(1, 2));
  V.Add(new pair(4, 6));
  V.Add(new pair(2, 1));
  V.Add(new pair(9, 6));
  V.Add(new pair(9, 3));
  V.Add(new pair(4, 3));
 
  MissingPoint(V, N);
}
}
 
// This code is contributed by Rajput-Ji

//JavaScript Program to implement
// the above approach
 
function MissingPoint(V, N)
{
    let mp = new Map();
    for (let i = 0; i < V.length; i++) {
        if(mp.has(V[i][0])){
            mp.set(V[i][0], mp.get(V[i][0]) + 1);
             
        }
        else{
            mp.set(V[i][0], 1);
        }
    }
 
    let x, y;
    for (const [key, value] of mp.entries()) {
        if (value % 2 == 1) {
            x = key;
            break;
        }
    }
    mp.clear();
    for (let i = 0; i < V.length; i++) {
        if(mp.has(V[i][1])){
            mp.set(V[i][1], mp.get(V[i][1]) + 1);  
        }
        else{
            mp.set(V[i][1], 1);
        }
    }
 
    for (const [key, value] of mp) {
        if (value % 2 == 1) {
            y = key;
            break;
        }
    }
 
    console.log(x, y);
}
 
// Driver Code
// Number of rectangles
let N = 2;
 
// Stores the coordinates
let V = new Array();
 
// Insert the coordinates
V.push([1, 1]);
V.push([1, 2]);
V.push([4, 6]);
V.push([2, 1]);
V.push([9, 6]);
V.push([9, 3]);
V.push([4, 3]);
 
MissingPoint(V, N);
 
// The code is contributed by gautam goel (gautamgoel962)

2 2

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)