SPOJ - zadanie Sort1

Question

Witam, udało mi się zrobić zadanie Sort1 z polskiego SPOJ'a (link do zadania). Jednakże nie czuję się dobrze z tym rozwiązaniem, tzn. program dziala w czasie mniej wiecej kwadratowym i dla wiekszych testow program bedzie dzialal bardzo powoli. I odnosnie tego mam pytanie: czy da sie posortowac tablice obiektow ze wzgledu na ich parametry, tzn w moim przypadku czy jestem zmuszony tworzyc tablice tab (14. linia kodu):

float *tab=new float[n];

ktora przechowuje odleglosc punktu od pkt(0,0) ? Dzieki za wszystkie odpowiedzi z gory. :D

kod programu:

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct Punkt{
	string n;
	int x,y;
	float o;
};
int main(){
	int t,n,k; cin>>t;
	for(auto i=0; i<t; ++i){
		cin>>n;
		float *tab=new float[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));
			tab[j]=p[j].o;
		}
		sort(tab,tab+n);
		for(auto j=0; j<n; ++j){
			for(auto k=0; k<n; k++){
				if(p[k].o==tab[j]){
					cout<<p[k].n<<' '<<p[k].x<<' '<<p[k].y<<'\n';
					break;
				}
			}
		}
		delete [] tab;
		delete [] p;
	} 
}

 

Answer 1

Nie potrzebujesz dodatkowej tablicy. Posortuj punkty od razu po odległości:

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct Punkt {
    string n;
    int x, y;
    float o;
};

bool point_less(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 = pow(p[j].x, 2) + pow(p[j].y, 2);
        }

        sort(p, p + n, point_less); // sort(p, p + n, [](auto p1, auto p2){ return p1.o < p2.o; })

        for (auto j = 0; j < n; j++) {
            cout << p[j].n << ' ' << p[j].x << ' ' << p[j].y << '\n';
        }

        delete[] p;
    }
}

Comments

dzieki