#include <iostream>
using namespace std;
class CPoint {
public:
void set(int a_, int b_) { a = a_; b = b_; }
bool small(const CPoint &p) {
unsigned long long int la = b;
unsigned long long int lb = p.a;
unsigned long long int lb2 = p.b;
unsigned long long int l = la * lb + lb2;
la = p.b;
lb = a;
lb2 = b;
unsigned long long int r = la * lb + lb2;
return l < r;
}
bool big(const CPoint &p) {
unsigned long long int la = b;
unsigned long long int lb = p.a;
unsigned long long int lb2 = p.b;
unsigned long long int l = la * lb + lb2;
la = p.b;
lb = a;
lb2 = b;
unsigned long long int r = la * lb + lb2;
return l > r;
}
int a, b;
};
void qsort(CPoint* arr, int start, int end) {
CPoint p = arr[(start + end) / 2];
int s = start;
int e = end;
while (s <= e) {
while (arr[s].small(p)) { s++; }
while (arr[e].big(p)) { e--; }
if (s <= e) {
CPoint t = arr[s];
arr[s] = arr[e];
arr[e] = t;
s++;
e--;
}
}
if (start < e) {
qsort(arr, start, e);
}
if (s < end) {
qsort(arr, s, end);
}
}
CPoint p[200001];
int main()
{
int TC = 0;
cin >> TC;
for (int tc = 1; tc <= TC; tc++) {
int N = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> p[i].a >> p[i].b;
}
qsort(p, 0, N - 1);
cout << "# " << tc << " " << N << endl;
for (int i = 0; i < N; i++) {
cout << p[i].a << " " << p[i].b << endl;
}
}
return 0;
}
'Coding > CPP 삽질기' 카테고리의 다른 글
[C] Binary search (0) | 2020.12.06 |
---|---|
Bit 연산 정리 (0) | 2016.08.20 |
가장 넓은 직사각형 구하는 알고리즘 ( O(MN) ) (0) | 2016.04.13 |