Spoj, zadanie Sort 1

Question

Cześć

SPOJ nie przyjmuje kodu twierdząc, że odpowiedź jest błędna

#include <iostream>
#include <math.h>

using namespace std;

void f(double w[],int x[],int y[],string nazwa[], int n)
{
    for(int i=0; i<n; i++)
        for(int j=1; j<n-i; j++) //pętla wewnętrzna
            if(w[j-1]>w[j])
            {
                swap(nazwa[j-1],nazwa[j]);
                swap(x[j-1],x[j]);
                swap(y[j-1],y[j]);
            }
                //zamiana miejscami
                //swap(tab[j-1], tab[j]);
}

int main()
{
    int t;
    int n;

    cin >> t;

    for(int i = 0; i < t; i ++)
    {
        cin >> n;
        int* x = new int[n];
        int* y = new int[n];
        string* nazwa = new string[n];
        double* w = new double[n];//wynik

        for(int j = 0; j < n; j ++)
        {
            cin >> nazwa[j] >> x[j] >> y[j];
            w[j] = sqrt(x[j]*x[j]+y[j]*y[j]);
        }

        f(w,x,y,nazwa,n);

        for(int j = 0; j < n; j++)
        {
            cout << nazwa[j] << x[j] << y[j] << endl;
        }

        cout << endl;

        delete []x;
        delete []y;
        delete []nazwa;
        delete []w;
    }

    return 0;
}

Pomysł mój polegał na tym, żeby wraz z sortowaniem wyniku sqrt(x,y), sortować tak samo nazwę, x i y, dzięki czemu wszystkie te zmienne, które zostały wprwadzone w tym samym czasie były na tych samych indeksach przy wyświetlaniu.

Próbowałem coś kombinować z wyświetlaniem tekstu tj. dodwać endl; lub spację między kolejnymi zmiennymi ale SPOJ nadal nie zalicza.Przejrzałem także bliźniacze wątki, ale nie znalazłem odpowiedzi

Proszę o pomoc.

Answer 1

a nie lepiej zrobić jakąś strukturkę i posortować wbudowaną funkcją sort()?

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct Punkt{
	string n;
	int x,y;
	float o;
};
bool f(Punkt p1,Punkt p2){
	return p1.o<p2.o;
}
int main(){
	int t,n,k; cin>>t;
	for(auto i=0; i<t; ++i){
		cin>>n;
		Punkt *p=new Punkt[n];
		for(auto j=0; j<n; ++j){
			cin>>p[j].n>>p[j].x>>p[j].y;
			p[j].o=sqrt(pow(p[j].x,2)+pow(p[j].y,2));
		}
		sort(p,p+n,f);
		for(auto j=0; j<n; ++j){
			cout<<p[j].n<<' '<<p[j].x<<' '<<p[j].y<<'\n';
		}
		delete [] p;
	} 
} 

 

Answer 2

Cześć,

Wpadłem na taki sam pomysł jak Ty, natomiast nie korzystałem z alokacji dynamicznej tylko po prostu zadeklarowałem tablice:

cin >> n; //liczba punktów
int odl[n];
string punkt[n];

Następnie przekształcałem współrzędne punktów w pętli na stringi i skorzystałem z procedury sortowania bąbelkowego, którego kod można znaleźć na kursie Pana Mirosława i przekształciłem go właśnie tak jak wspomniałeś, czyli indeks nazwy zmieniał się wraz z indeksem wyniku (odległości punktu od środka układu współrzędnych):

void sortowanie_babelkowe_odlipunktu(int *tab, string *pkt, int m) //gdzie m to ilość punktów
{
    for(int i=1; i<m; i++)
    {
        for(int j=m-1; j>=1; j--)
        {
            if(tab[j]<tab[j-1])
            {
                int bufor;
                string bufor2;
                bufor=tab[j-1];
                bufor2=pkt[j-1];
                tab[j-1]=tab[j];
                pkt[j-1]=pkt[j];
                tab[j]=bufor;
                pkt[j]=bufor2;
            }
        }
    }
}

Niemniej jednak, proponowałbym najpierw usunięcie funkcji sqrt(); - pierwiastka, bo to w moim przypadku bruździło, a jest zbędna w tym przypadku. Dodatkowo, jeśli się nie mylę to funkcja swap(); wymaga biblioteki <string>, której u Ciebie brakuje.

Trochę minęło od zadania Twojego pytania, ale może komuś innemu przydadzą się te uwagi :).

Pozdrawiam.

Comments

Niemniej jednak, proponowałbym najpierw usunięcie funkcji sqrt();

To jest słuszna uwaga, ale reszta niezbyt.