Zad F

Wzorcówka

#include <cstdio>

using namespace std;

struct peak
{
  int n;
  int x;
  int y;
};

bool less(peak q, peak r)
{
  long long a = (long long)q.x*(long long)r.y;
  long long b = (long long)q.y*(long long)r.x;
  return a < b || a == b && q.y<r.y;
}

void QuickSort(peak P[], int u, int v)
{
//  printf("%d %d\n",u,v);
  int i = u;
  int j = v;
  peak key = P[(u+v)/2];
  while(i<=j)
  {
    while(less(P[i],key))
      i++;
    while(less(key,P[j]))
      j--;
    if (i<=j)
    {
      peak temp = P[i];
      P[i] = P[j];
      P[j] = temp;
      i++; j--;
    }
  }
  if (u<j)
    QuickSort(P,u,j);
  if (i<v)
    QuickSort(P,i,v);
}

int main()
{
  peak P[1000*1001];
  int TT,n;
  scanf("%d",&TT);
  while(TT--)
  {
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
      P[i].n = i;
      scanf("%d %d",&P[i].x,&P[i].y);
    }
    QuickSort(P,0,n-1);
    for(int i=0; i<n; i++)
      printf("%d\n",P[i].n+1);
  }
}