znajdź najbliższą lokalizację od oryginalnego punktu

Question

Załóżmy, że mamy następujący problem - chcemy odczytać zestaw współrzędnych (x, y) i nazwę, a następnie posortować je w kolejności, zwiększając odległość od początku (0, 0). Oto algorytm które wykorzystują najprostsze sortowanie bąbelkowe:

#include<iostream> 
    #include <algorithm> 
    using namespace std; 
    struct point{ 
     float x; 
     float y; 
     char name[20]; 

     }; 
     float dist(point p){ 
      return p.x*p.x+p.y*p.y; 
      } 
     void sorting(point pt[],int n){ 
      bool doMore = true; 
     while (doMore) { 
      doMore = false; // Assume no more passes unless exchange made. 
      for (int i=0; i<n-1; i++) { 
       if (dist(pt[i]) > dist(pt[i+1])) { 
        // Exchange elements 
        point temp = pt[i]; pt[i] = pt[i+1]; pt[i+1] = temp; 
        doMore = true; // Exchange requires another pass. 
       } 
      } 
     } 

     } 
     void display(point pt[],int n){ 
      for (int i=0;i<n;i++){ 
       cout<<pt[i].name<< " "; 
        } 
     } 
    int main(){ 
    point pts[1000]; 
    int n=0; 

    while (cin>>pts[n].name>>pts[n].x>>pts[n].y){ 
     n++; 

    } 
    sorting(pts,n); 
    display(pts,n); 

    return 0; 
    } 

Ale chcę napisać algorytm sortowania STL zamiast bubble sortowania. Jak to zrobić?

Mam na myśli to, jak powinienem używać funkcji dist w algorytmie sortowania STL?

Answer 1

Funkcja sortowania STL std::sort może przyjąć funkcję porównywania zdefiniowaną przez użytkownika (lub obiekt funkcji) jako opcjonalny trzeci argument. Więc jeśli masz swoje przedmioty w np

vector<point> points; 

można sortować je przez wywołanie:

sort(points.begin(), points.end(), my_comp); 

gdzie my_comp() jest funkcją z następującym prototypie:

bool my_comp(const point &a, const point &b) 

Answer 2

#include <algorithm> 

bool sort_by_dist(point const& p1, point const& p2) { 
    return dist(p1) < dist(p2); 
} 

... 

std::sort(pt, pt + n, sort_by_dist);