#include<iostream>
#include<cmath>
using namespace std;
class points {
public :
float x, y, distance;
string name;
} ;
void swap( points tab[ ] , int a, int b) ;
int median( points tab[ ] , int beginning, int end) ;
int partition( points tab[ ] , int left, int pivot) {
int new_pivot = median( tab, left, pivot) ;
int i= left;
int j= pivot;
while ( i<= j) {
while ( tab[ i] .distance < tab[ new_pivot] .distance ) {
i++ ;
}
while ( tab[ j] .distance > tab[ new_pivot] .distance ) {
j-- ;
}
if ( i<= j) {
swap( tab, i, j) ;
i++ ;
j-- ;
}
}
return new_pivot;
}
void quicksort( points tab[ ] , int left, int pivot) {
if ( left< pivot) {
int new_pivot = partition( tab, left, pivot) ;
quicksort( tab, left, new_pivot- 1 ) ;
quicksort( tab, new_pivot+ 1 , pivot) ;
}
}
int main( ) {
int how_many_tests;
cin >> how_many_tests;
for ( int aa= 0 ; aa< how_many_tests; aa++ ) {
int how_many_points;
cin >> how_many_points;
points tab[ how_many_points] ;
for ( int a= 0 ; a< how_many_points; a++ ) {
cin >> tab[ a] .name >> tab[ a] .x >> tab[ a] .y ;
tab[ a] .distance = sqrt ( tab[ a] .x * tab[ a] .x + tab[ a] .y * tab[ a] .y ) ;
}
/*
//prints out the entire tab for debugging
for (int a=0; a<how_many_points; a++) {
cout << tab[a].name << " " << tab[a].x << " " << tab[a].y << " " << tab[a].distance << endl;
}
*/
quicksort( tab, 0 , how_many_points- 1 ) ;
/*
//prints out entire tab again but sorted (hopefully)
for (int a=0; a<how_many_points; a++) {
cout << tab[a].name << " " << tab[a].x << " " << tab[a].y << " " << tab[a].distance << endl;
}
*/
for ( int a= 0 ; a< how_many_points; a++ ) {
cout << tab[ a] .name << " " << tab[ a] .x << " " << tab[ a] .y << endl;
}
cout << endl;
}
}
//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.
//i am doing this because i am trying to implement the quicksort using the pivot median of three method.
int median( points tab[ ] , int beginning, int end) {
float a = tab[ beginning] .distance ;
float b = tab[ end] .distance ;
float c = tab[ ( ( end+ beginning) / 2 ) ] .distance ;
//cout << "a: " << a << ", b: " << b << ", c: " << c << " ";
if ( a> b && a> c) {
if ( b> c) {
return ( end+ beginning) / 2 ;
} else {
return end;
}
} else if ( b> a && b> c) {
if ( a> c) {
return beginning;
} else {
return end;
}
} else if ( c> a && c> b) {
if ( a> b) {
return beginning;
} else {
return ( end+ beginning) / 2 ;
}
} else {
//hopefully it should never get to this point if ive done everything right
//because a, b and c should all be different
return 0 ;
}
}
void swap( points tab[ ] , int a, int b) {
float temp_x = tab[ a] .x ;
float temp_y = tab[ a] .y ;
float temp_distance = tab[ a] .distance ;
string temp_name = tab[ a] .name ;
tab[ a] .x = tab[ b] .x ;
tab[ a] .y = tab[ b] .y ;
tab[ a] .distance = tab[ b] .distance ;
tab[ a] .name = tab[ b] .name ;
tab[ b] .x = temp_x;
tab[ b] .y = temp_y;
tab[ b] .distance = temp_distance;
tab[ b] .name = temp_name;
return ;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNtYXRoPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIHBvaW50cyB7CiAgICBwdWJsaWM6CiAgICBmbG9hdCB4LCB5LCBkaXN0YW5jZTsKICAgIHN0cmluZyBuYW1lOwp9OwoKdm9pZCBzd2FwKHBvaW50cyB0YWJbXSwgaW50IGEsIGludCBiKTsKCmludCBtZWRpYW4ocG9pbnRzIHRhYltdLCBpbnQgYmVnaW5uaW5nLCBpbnQgZW5kKTsKCmludCBwYXJ0aXRpb24ocG9pbnRzIHRhYltdLCBpbnQgbGVmdCwgaW50IHBpdm90KSB7CiAgICAKICAgIGludCBuZXdfcGl2b3QgPSBtZWRpYW4odGFiLCBsZWZ0LCBwaXZvdCk7CiAgICBpbnQgaT1sZWZ0OwogICAgaW50IGo9cGl2b3Q7CgogICAgd2hpbGUgKGk8PWopIHsKICAgICAgICAKICAgICAgICB3aGlsZSAodGFiW2ldLmRpc3RhbmNlPHRhYltuZXdfcGl2b3RdLmRpc3RhbmNlKSB7CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9CiAgICAgICAKICAgICAgICB3aGlsZSAodGFiW2pdLmRpc3RhbmNlPnRhYltuZXdfcGl2b3RdLmRpc3RhbmNlKSB7CiAgICAgICAgICAgIGotLTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaWYgKGk8PWopIHsKICAgICAgICAgICAgc3dhcCh0YWIsIGksIGopOwogICAgICAgICAgICBpKys7CiAgICAgICAgICAgIGotLTsKICAgICAgICB9CiAgICAgICAgCiAgICB9CiAgICByZXR1cm4gbmV3X3Bpdm90Owp9Cgp2b2lkIHF1aWNrc29ydChwb2ludHMgdGFiW10sIGludCBsZWZ0LCBpbnQgcGl2b3QpIHsKCiAgICBpZiAobGVmdDxwaXZvdCkgewoKICAgICAgICBpbnQgbmV3X3Bpdm90ID0gcGFydGl0aW9uKHRhYiwgbGVmdCwgcGl2b3QpOwogICAgICAgIHF1aWNrc29ydCh0YWIsIGxlZnQsIG5ld19waXZvdC0xKTsKICAgICAgICBxdWlja3NvcnQodGFiLCBuZXdfcGl2b3QrMSwgcGl2b3QpOwoKICAgIH0KCn0KCmludCBtYWluKCkgewogICAgCiAgICBpbnQgaG93X21hbnlfdGVzdHM7CiAgICBjaW4gPj4gaG93X21hbnlfdGVzdHM7CgogICAgZm9yIChpbnQgYWE9MDsgYWE8aG93X21hbnlfdGVzdHM7IGFhKyspIHsKCiAgICAgICAgaW50IGhvd19tYW55X3BvaW50czsKICAgICAgICBjaW4gPj4gaG93X21hbnlfcG9pbnRzOwogICAgICAgIAogICAgICAgIHBvaW50cyB0YWJbaG93X21hbnlfcG9pbnRzXTsKCiAgICAgICAgZm9yIChpbnQgYT0wOyBhPGhvd19tYW55X3BvaW50czsgYSsrKSB7CiAgICAgICAgICAgIGNpbiA+PiB0YWJbYV0ubmFtZSA+PiB0YWJbYV0ueCA+PiB0YWJbYV0ueTsKICAgICAgICAgICAgdGFiW2FdLmRpc3RhbmNlID0gc3FydCh0YWJbYV0ueCp0YWJbYV0ueCArIHRhYlthXS55KnRhYlthXS55KTsKICAgICAgICB9CgogICAgICAgIC8qCiAgICAgICAgLy9wcmludHMgb3V0IHRoZSBlbnRpcmUgdGFiIGZvciBkZWJ1Z2dpbmcKICAgICAgICBmb3IgKGludCBhPTA7IGE8aG93X21hbnlfcG9pbnRzOyBhKyspIHsKICAgICAgICAgICAgY291dCA8PCB0YWJbYV0ubmFtZSA8PCAiICIgPDwgdGFiW2FdLnggPDwgIiAiIDw8IHRhYlthXS55IDw8ICIgIiA8PCB0YWJbYV0uZGlzdGFuY2UgPDwgZW5kbDsKICAgICAgICB9CiAgICAgICAgKi8KCiAgICAgICAgcXVpY2tzb3J0KHRhYiwgMCwgaG93X21hbnlfcG9pbnRzLTEpOwogICAgICAgCiAgICAgICAgLyoKICAgICAgICAvL3ByaW50cyBvdXQgZW50aXJlIHRhYiBhZ2FpbiBidXQgc29ydGVkIChob3BlZnVsbHkpCiAgICAgICAgZm9yIChpbnQgYT0wOyBhPGhvd19tYW55X3BvaW50czsgYSsrKSB7CiAgICAgICAgICAgIGNvdXQgPDwgdGFiW2FdLm5hbWUgPDwgIiAiIDw8IHRhYlthXS54IDw8ICIgIiA8PCB0YWJbYV0ueSA8PCAiICIgPDwgdGFiW2FdLmRpc3RhbmNlIDw8IGVuZGw7CiAgICAgICAgfQogICAgICAgICovCgogICAgICAgIGZvciAoaW50IGE9MDsgYTxob3dfbWFueV9wb2ludHM7IGErKykgewogICAgICAgICAgICBjb3V0IDw8IHRhYlthXS5uYW1lIDw8ICIgIiA8PCB0YWJbYV0ueCA8PCAiICIgPDwgdGFiW2FdLnkgPDwgZW5kbDsKICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgZW5kbDsKCiAgICB9CiAgICAKfQoKCi8vdGhpcyBpcyBtZWFudCB0byByZXR1cm4gdGhlIGludGVnZXIgaSBvZiB0aGUgbWVkaWFuIG9mIHRhYltiZWdpbm5pbmddLCB0YWJbZW5kXSBhbmQgdGFiWyhiZWdpbm5pbmcrZW5kKS8yXSB3aGVyZSB0YWJbaV0gaXMgdGhlIG1lZGlhbiBvZiB0aG9zZSB0aHJlZS4KLy9pIGFtIGRvaW5nIHRoaXMgYmVjYXVzZSBpIGFtIHRyeWluZyB0byBpbXBsZW1lbnQgdGhlIHF1aWNrc29ydCB1c2luZyB0aGUgcGl2b3QgbWVkaWFuIG9mIHRocmVlIG1ldGhvZC4KaW50IG1lZGlhbihwb2ludHMgdGFiW10sIGludCBiZWdpbm5pbmcsIGludCBlbmQpIHsKICAgIGZsb2F0IGEgPSB0YWJbYmVnaW5uaW5nXS5kaXN0YW5jZTsKICAgIGZsb2F0IGIgPSB0YWJbZW5kXS5kaXN0YW5jZTsKICAgIGZsb2F0IGMgPSB0YWJbKChlbmQrYmVnaW5uaW5nKS8yKV0uZGlzdGFuY2U7CgogICAgLy9jb3V0IDw8ICJhOiAiIDw8IGEgPDwgIiwgYjogIiA8PCBiIDw8ICIsIGM6ICIgPDwgYyA8PCAiICI7CgogICAgaWYgKGE+YiAmJiBhPmMpIHsKICAgICAgICBpZiAoYj5jKSB7CiAgICAgICAgICAgIHJldHVybiAoZW5kK2JlZ2lubmluZykvMjsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gZW5kOwogICAgICAgIH0KICAgIH0gZWxzZSBpZiAoYj5hICYmIGI+YykgewogICAgICAgIGlmIChhPmMpIHsKICAgICAgICAgICAgcmV0dXJuIGJlZ2lubmluZzsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gZW5kOwogICAgICAgIH0KICAgIH0gZWxzZSBpZiAoYz5hICYmIGM+YikgewogICAgICAgIGlmIChhPmIpIHsKICAgICAgICAgICAgcmV0dXJuIGJlZ2lubmluZzsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByZXR1cm4gKGVuZCtiZWdpbm5pbmcpLzI7CiAgICAgICAgfQogICAgfSBlbHNlIHsKICAgICAgICAvL2hvcGVmdWxseSBpdCBzaG91bGQgbmV2ZXIgZ2V0IHRvIHRoaXMgcG9pbnQgaWYgaXZlIGRvbmUgZXZlcnl0aGluZyByaWdodAogICAgICAgIC8vYmVjYXVzZSBhLCBiIGFuZCBjIHNob3VsZCBhbGwgYmUgZGlmZmVyZW50CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICAKfQoKdm9pZCBzd2FwKHBvaW50cyB0YWJbXSwgaW50IGEsIGludCBiKSB7CiAgICAKICAgIGZsb2F0IHRlbXBfeCA9IHRhYlthXS54OwogICAgZmxvYXQgdGVtcF95ID0gdGFiW2FdLnk7CiAgICBmbG9hdCB0ZW1wX2Rpc3RhbmNlID0gdGFiW2FdLmRpc3RhbmNlOwogICAgc3RyaW5nIHRlbXBfbmFtZSA9IHRhYlthXS5uYW1lOwoKICAgIHRhYlthXS54ID0gdGFiW2JdLng7CiAgICB0YWJbYV0ueSA9IHRhYltiXS55OwogICAgdGFiW2FdLmRpc3RhbmNlID0gdGFiW2JdLmRpc3RhbmNlOwogICAgdGFiW2FdLm5hbWUgPSB0YWJbYl0ubmFtZTsKCiAgICB0YWJbYl0ueCA9IHRlbXBfeDsKICAgIHRhYltiXS55ID0gdGVtcF95OwogICAgdGFiW2JdLmRpc3RhbmNlID0gdGVtcF9kaXN0YW5jZTsKICAgIHRhYltiXS5uYW1lID0gdGVtcF9uYW1lOwoKICAgIAogICAgcmV0dXJuOwoKfQ==