Untitled
plain_text
22 days ago
2.8 kB
5
Indexable
Never
/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog. Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; int manhatten(vector<vector<int>>&matrix,int x,int y) { int sum=0; for(int i=0;i<matrix.size();i++) { int x1=matrix[i][0],x2=matrix[i][2],y1=matrix[i][1],y2=matrix[i][3]; int p1,p2; if(x1<x&&x2>x)p1=x; else if(x1<x&&x2<x)p1=max(x1,x2); else if(x1>x&&x2>x)p1=min(x1,x2); else p1=x; if(y1<y&&y2>y)p2=y; else if(y1<y&&y2<y)p2=max(y1,y2); else if(y1>y&&y2>y)p2=min(y1,y2); else p2=y; int dis=abs(x-p1)+abs(y-p2); sum+=dis; } return sum; } pair<int,int> func(vector<vector<int>>&matrix) { vector<int>xaxis; vector<int>yaxis; for(int i=0;i<matrix.size();i++) { xaxis.push_back(matrix[i][0]); xaxis.push_back(matrix[i][2]); yaxis.push_back(matrix[i][1]); yaxis.push_back(matrix[i][3]); } sort(xaxis.begin(),xaxis.end()); sort(yaxis.begin(),yaxis.end()); int size=xaxis.size(); pair<int,int>pr; int mid=size/2; if(size%2==0) { int mini=manhatten(matrix,xaxis[mid],yaxis[mid]); int mini1=manhatten(matrix,xaxis[mid-1],yaxis[mid-1]); if(mini<mini1)return {xaxis[mid],yaxis[mid]}; else if(mini1<mini)return {xaxis[mid-1],yaxis[mid-1]}; else { if(xaxis[mid]<xaxis[mid-1])return{xaxis[mid],yaxis[mid]}; else if(xaxis[mid]>xaxis[mid-1])return {xaxis[mid-1],yaxis[mid-1]}; else { if(yaxis[mid]<yaxis[mid-1])return{xaxis[mid],yaxis[mid]}; else return {xaxis[mid-1],yaxis[mid-1]}; } } } else { pr.first=xaxis[mid]; pr.second=yaxis[mid]; } return pr; } int main() { //TC 1 vector<vector<int>>matrix{{0,0,2,0},{0,2,3,2},{3,1,3,4}}; auto x=func(matrix); cout<<x.first<<" "<<x.second<<endl; //TC 2 vector<vector<int>>matrix1{{4,2,4,5},{3,3,5,3},{0,3,0,4}}; auto x1=func(matrix1); cout<<x1.first<<" "<<x1.second<<endl; //TC 3 vector<vector<int>>matrix2{{2,4,2,0},{2,1,0,1},{4,3,4,4},{5,5,4,5}}; auto x2=func(matrix2); cout<<x2.first<<" "<<x2.second<<endl; return 0; }