# The Way to a Friends House Is Never Too Long

Can someone post the algorithm to solve this problem ?

1 Like

Modify merge sort to get the required order of points and then calculate distance.
In merge sort when the value of x coordinates become equal, check for y coordinates to arrange in required order.

``````struct Points{
int x;
int y;
};
void merge(int b,int m,int e){
Points temp[n];
int i=b,j=m+1,k=b;
while(i<=m && j<=e){
if(p[i].x<p[j].x)
temp[k++] = p[i++];
else if(p[j].x<p[i].x)
temp[k++]=p[j++];
else if(p[i].x==p[j].x){
if(p[i].y>=p[j].y)
temp[k++]=p[i++];
else if(p[j].y>p[i].y)
temp[k++]=p[j++];
}
}
while(i<=m)
temp[k++]=p[i++];
while(j<=e)
temp[k++]=p[j++];
for(int i=b;i<=e;i++)
p[i]=temp[i];
}
void merge_sort(int b,int e){
if(b<e){
int m=(b+e)/2;
merge_sort(b,m);
merge_sort(m+1,e);
merge(b,m,e);
}
}``````

make a vector using pair<int,int> as its data type and store all x and y in that vector. Then, sort the vector using comparator function(Shown Below) and iterate one by one vector array and use Distance Formulaâ€¦
Note - Take all values in Double or float except N and T

Once u calculate the ans.

USE THIS : cout << fixed << showpoint ;
cout << setprecision(2) ; // this will print the values, after decimals. Here it is 2
cout<<â€śThe value U findâ€ť;

Now, give it a try again and if not able to solve then see the code .

#include<bits/stdc++.h>
#define M 1000000007
using namespace std;
typedef long long int ll;
bool comp(pair<double ,double >a,pair<double ,double >b)
{
if(a.first<b.first)
return true;
else if(a.first==b.first)
{
if(a.second>b.second)
return true;
else
return false;
}
else
{
return false;
}
}
int main()
{
int t;
cin>>t;
while(tâ€“)
{
int n;
cin>>n;
vector<pair<double ,double >>p;
while(nâ€“)
{
double a,b;
cin>>a>>b;
p.push_back(make_pair(a,b));

``````   }
sort(p.begin(),p.end(),comp);

double val=0;
for(double  i=0;i<p.size()-1;i++)
{
double  a,b;
a=p[i].first;
b=p[i].second;
double  c=p[i+1].first;
double  d=p[i+1].second;
val+= sqrt(pow(c-a,2)+pow(b-d,2));
``````

// cout<<â€śval=â€ť<<val<<endl;
}
cout<<fixed<<showpoint;
cout<<setprecision(2);
cout<<val<<endl;

``````}
``````

}