• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

SPOJ - zadanie Sort1

VPS Starter Arubacloud
0 głosów
194 wizyt
pytanie zadane 30 czerwca 2022 w C i C++ przez polandonion Mądrala (6,970 p.)
edycja 30 czerwca 2022 przez polandonion

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

 

1 odpowiedź

+1 głos
odpowiedź 30 czerwca 2022 przez Great Stary wyjadacz (12,300 p.)
wybrane 30 czerwca 2022 przez polandonion
 
Najlepsza

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;
    }
}
komentarz 30 czerwca 2022 przez polandonion Mądrala (6,970 p.)
dzieki

Podobne pytania

0 głosów
2 odpowiedzi 629 wizyt
pytanie zadane 12 sierpnia 2020 w SPOJ przez Arek04 Użytkownik (700 p.)
0 głosów
1 odpowiedź 440 wizyt
pytanie zadane 12 stycznia 2019 w SPOJ przez WireNess Stary wyjadacz (11,240 p.)
0 głosów
1 odpowiedź 411 wizyt
pytanie zadane 26 października 2018 w SPOJ przez Piotr Błaszczak Bywalec (2,890 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...