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++
// 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
// 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
# 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#
// 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
//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)
Publicación traducida automáticamente
Artículo escrito por sakshivarshney0910 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA