Given 4N-1 vertices of N rectangles find the missing vertex.

You have been given N Casterian Coordinate axis-parallel rectangles, but one of its vertexes is missing, i.e. Out of 4N vertex, you have only been given 4N-1 vertices.  You need to find the missing vertex.

->The rectangles can overlap

->All the vertices are unique i.e no two vertex overlap

Example:

INPUT:

N=1

vertices = (2,2), (3,2), (2,3)

Output: 

The missing vertex is: (3,3)

Explanation: N=1 means we have been given just a single rectangle, the three vertices given to us are : (2,2), (3,2), (2,3). Plotting the points on the XY coordinate axes we can see that the missing vertex will be (3,3).

Approach:

A possible solution is by employing the use of HashSet. We create two HashSet: one for the x coordinates and the other for the y coordinates.

Now loop through the x_cordinates in the input vertices array, if the 'x' coordinate is already present in the HashSet then remove it from the HashSet or else insert it to the HashSet. 

Again loop through the y_cordinates in the input vertices array, if the 'y' coordinate is already present in the HashSet then remove it from the HashSet or else insert it to the HashSet. 

	#include<stdio.h>
	using namespace std;
	pair<int,int> findMissingVertex(vector<pair<int,int>> &vertices, int n)
	{
	// Declaring hashsets for X and Y coordinates
	set<int> hashset_x;
	set<int> hashset_y;
	// Loop through the given 4N-1 vertices
	for(int i=0;i<4*n-1;i++)
	{
	// x, y are cordinates of the given point
	int x = vertices[i].first;
	int y = vertices[i].second;
	// Check if the current X coordinate is already present in the X Coordinate hashset
	if(hashset_x.find(x) != hashset_x.end())
	{
	// If it is already present in the hashset, then remove it from the hashset
	hashset_x.erase(x);
	}
	else
	{
	// If the coordinate was not present in the hashset, then add it to the hashset
	hashset_x.insert(x);
	}
	// Do the above steps for Y coordinates also
	if(hashset_y.count(y))
	{
	hashset_y.erase(y);
	}
	else
	{
	hashset_y.insert(y);
	}
	}
	// The missing vertex will be the coordinates remaining in the hashsets
	pair<int,int> missingVertex = make_pair(*hashset_x.begin(), *hashset_y.begin());
	return missingVertex;
	}
	int main()
	{
	int N =1;
	vector<pair<int,int>> vertices{make_pair(2,2), make_pair(3,2), make_pair(2,3)};
	pair<int,int> missingVertex = findMissingVertex(vertices, N);
	cout<<"The missing vertex is: ("<<missingVertex.first<<" , "<<missingVertex.second<<")"<<endl;
	}

view raw rectangles.cpp hosted with ❤ by GitHub

Visit me at: http://www.caffeine-coated.codes/