fork(5) download 
  1. #include<iostream>
  2. #include<cmath>
  3.  
  4. using namespace std;
  5.  
  6. class points {
  7.     public:
  8.     float x, y, distance;
  9.     string name;
  10. };
  11.  
  12. void swap(points tab[], int a, int b);
  13.  
  14. int median(points tab[], int beginning, int end);
  15.  
  16. int partition(points tab[], int left, int pivot) {
  17.  
  18.     int new_pivot = median(tab, left, pivot);
  19.     int i=left;
  20.     int j=pivot;
  21.  
  22.     while (i<=j) {
  23.  
  24.         while (tab[i].distance<tab[new_pivot].distance) {
  25.             i++;
  26.         }
  27.  
  28.         while (tab[j].distance>tab[new_pivot].distance) {
  29.             j--;
  30.         }
  31.  
  32.         if (i<=j) {
  33.             swap(tab, i, j);
  34.             i++;
  35.             j--;
  36.         }
  37.  
  38.     }
  39.     return new_pivot;
  40. }
  41.  
  42. void quicksort(points tab[], int left, int pivot) {
  43.  
  44.     if (left<pivot) {
  45.  
  46.         int new_pivot = partition(tab, left, pivot);
  47.         quicksort(tab, left, new_pivot-1);
  48.         quicksort(tab, new_pivot+1, pivot);
  49.  
  50.     }
  51.  
  52. }
  53.  
  54. int main() {
  55.  
  56.     int how_many_tests;
  57.     cin >> how_many_tests;
  58.  
  59.     for (int aa=0; aa<how_many_tests; aa++) {
  60.  
  61.         int how_many_points;
  62.         cin >> how_many_points;
  63.  
  64.         points tab[how_many_points];
  65.  
  66.         for (int a=0; a<how_many_points; a++) {
  67.             cin >> tab[a].name >> tab[a].x >> tab[a].y;
  68.             tab[a].distance = sqrt(tab[a].x*tab[a].x + tab[a].y*tab[a].y);
  69.         }
  70.  
  71.         /*
  72.         //prints out the entire tab for debugging
  73.         for (int a=0; a<how_many_points; a++) {
  74.             cout << tab[a].name << " " << tab[a].x << " " << tab[a].y << " " << tab[a].distance << endl;
  75.         }
  76.         */
  77.  
  78.         quicksort(tab, 0, how_many_points-1);
  79.  
  80.         /*
  81.         //prints out entire tab again but sorted (hopefully)
  82.         for (int a=0; a<how_many_points; a++) {
  83.             cout << tab[a].name << " " << tab[a].x << " " << tab[a].y << " " << tab[a].distance << endl;
  84.         }
  85.         */
  86.  
  87.         for (int a=0; a<how_many_points; a++) {
  88.             cout << tab[a].name << " " << tab[a].x << " " << tab[a].y << endl;
  89.         }
  90.  
  91.         cout << endl;
  92.  
  93.     }
  94.  
  95. }
  96.  
  97.  
  98. //this is meant to return the integer i of the median of tab[beginning], tab[end] and tab[(beginning+end)/2] where tab[i] is the median of those three.
  99. //i am doing this because i am trying to implement the quicksort using the pivot median of three method.
  100. int median(points tab[], int beginning, int end) {
  101.     float a = tab[beginning].distance;
  102.     float b = tab[end].distance;
  103.     float c = tab[((end+beginning)/2)].distance;
  104.  
  105.     //cout << "a: " << a << ", b: " << b << ", c: " << c << " ";
  106.  
  107.     if (a>b && a>c) {
  108.         if (b>c) {
  109.             return (end+beginning)/2;
  110.         } else {
  111.             return end;
  112.         }
  113.     } else if (b>a && b>c) {
  114.         if (a>c) {
  115.             return beginning;
  116.         } else {
  117.             return end;
  118.         }
  119.     } else if (c>a && c>b) {
  120.         if (a>b) {
  121.             return beginning;
  122.         } else {
  123.             return (end+beginning)/2;
  124.         }
  125.     } else {
  126.         //hopefully it should never get to this point if ive done everything right
  127.         //because a, b and c should all be different
  128.         return 0;
  129.     }
  130.  
  131. }
  132.  
  133. void swap(points tab[], int a, int b) {
  134.  
  135.     float temp_x = tab[a].x;
  136.     float temp_y = tab[a].y;
  137.     float temp_distance = tab[a].distance;
  138.     string temp_name = tab[a].name;
  139.  
  140.     tab[a].x = tab[b].x;
  141.     tab[a].y = tab[b].y;
  142.     tab[a].distance = tab[b].distance;
  143.     tab[a].name = tab[b].name;
  144.  
  145.     tab[b].x = temp_x;
  146.     tab[b].y = temp_y;
  147.     tab[b].distance = temp_distance;
  148.     tab[b].name = temp_name;
  149.  
  150.  
  151.     return;
  152.  
  153. }
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin 
2
3
A 0 0
C 5 5
B 1 -1

1 
X 1 1
stdout 
A 0 0
B 1 -1
C 5 5

X 1 1
https://ideone.com/muBxbB
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!