Coding/CPP 삽질기2017. 7. 13. 01:09

#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
Posted by chobocho