The Way to a Friends House Is Never Too Long

general
,
1

Can someone post the algorithm to solve this problem ?

1 Like
2

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);
    }
}
3

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 :slight_smile: .

#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;

}

}