Where am I going wrong in this problem?

general
, ,
1

The problem:

So basically, I tried to sort the given coordinates according to the following conditions:

  1. Sort all x’s in the ascending order. Greater the x, farther away it is positioned in the queue.

  2. During sorting, if the value of abscissa (x co-ordinate) of the two co-ordinates is same, then the co-ordinate having the smaller ordinate (y-co-ordinate) of the two gets pushed back in the queue.

(read the following example to understand it better)

Example:

If given inputs are : (0,0) (1,2) (1,4) (4,0)

The sorted input would be: (0,0) (1,4) (1,2) (4,0)

[Notice that (1.4) gets placed before (1,2) because 2 is smaller than 4]

ALGORITHM:

As you may have noticed, I basically used a revised version of bubblesort for this (in it’s crudest form: sort x’s in ascending order… if they are same, sort corresponding y’s in descending order). After sorting it, I have to find the distance between the starting and the ending co-ordinates (i.e. in my example, between (0,0) and (4,0))

So, all I have to do is find the distance between all adjacent co-ordinates (using basic forumla to find distance between 2 co-ordinates) and add them up to get the total distance from starting point to ending point.

BUT ALAS! I am getting WA :frowning: Can anyone kindly review the code or algorithm:

#include<iostream>
using namespace std;
#define MAX 10002
#include<math.h>
#include<iomanip>

void bubblesort(int x[], int y[], int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-i-1;j++ )
            if(x[j]>x[j+1] or (x[j]==x[j+1] and y[j]<y[j+1]))
            {
                int temp=x[j];
                x[j]=x[j+1];
                x[j+1]=temp;

                temp=y[j];
                y[j]=y[j+1];
                y[j+1]=temp;
            }
    }
}

long double dbtp(int xo, int yo, int xt, int yt)
{
    return sqrt( pow( (xo-xt), 2) + pow((yo-yt), 2) );
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n, x[MAX], y[MAX];
        cin>>n;

        for(int i=0;i<n;i++)
            cin>>x[i]>>y[i];

        bubblesort(x, y, n);

        long double dist=0;

        for(int i=0;i<n-1;i++)
            dist+=dbtp(x[i], y[i], x[i+1], y[i+1]); //distance between 2 co-ordinates

        cout << setprecision(2) << fixed; // to ensure I get upto 2 decimal places
        cout<< dist <<endl;

    }

    return 0;
}