PROBLEM NAME:
FINCOR
PROBLEM LINK:
DIFFICULTY:
Beginner, Simple
PREREQUISITES:
MATH, OBSERVATION
PROBLEM:
There are N 2D graphs, on each graph, there is one rectangle whose either one side is parallel to the x-axis or to the y-axis. In this mess, the mark the one drawing these missed on coordinate and is unable to find it. you are given all other coordinates of the rectangle to find the missing one?
Solution:
Problem Idea: If one side of is parallel to any axis in 2 D plane then both sides rectangle are parallel to x and y axis.
Suppose a rectangle has vertexes with name A,B,C,D and is parallel to axes of graph where A and C are diagonal vertexes lets assume coordinate of point A is (x,y) and point C is(a,b) with the help of these two coordinates we can find other coordinates because they lie on same line so B is(a,y) and D is (x,b)
A---------------------------B
|
|
|
|
D---------------------------C
try to do it on paper it will be easy.
so we concluded that coordinate with odd number of occurrence will be the missing point .
SOLUTION:
using sorting method:-
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
vector<int> x, y;
for(int i=0;i<4*n-1;++i) {
int X,Y;
cin>>X>>Y;
x.push_back(X);
y.push_back(Y);
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
int ans_x=-1,ans_y=-1;
auto find_odd=[&](vector<int>& x) -> int {
int i,j;
for(i=0;i<(int)x.size();i=j) {
j=i;
while(j<(int)x.size() && x[i]==x[j]) {
j++;
}
if((j-i)&1) return x[i];
}
return -1;
};
ans_x=find_odd(x);
ans_y=find_odd(y);
cout<<ans_x<<" "<<ans_y<<"\n";
}
return 0;
}
using map:-
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
map<int,int> X,Y;
for(int i=0;i<4*n-1;++i) {
int x,y;
cin>>x>>y;
X[x]++;
Y[y]++;
}
int ans_x=-1, ans_y=-1;
for(auto i:X) {
if(i.second&1) ans_x=i.first;
}
using bitwise:-
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
int ans_x=0, ans_y=0;
for(int i=0;i<4*n-1;++i) {
int x,y;
cin>>x>>y;
ans_x^=x;
ans_y^=y;
}
cout<<ans_x<<" "<<ans_y<<"\n";
}
return 0;
}