codisinmyvines

SborPosilok

Sep 26th, 2021
765
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <math.h>
  4. using namespace std;
  5. struct Coordinates
  6. {
  7.     int x;
  8.     int y;
  9. };
  10. void qsort(Coordinates*& c, int b, int e)
  11. {
  12.     int l = b, r = e;
  13.     double piv = sqrt((c[(l + r) / 2].x) * (c[(l + r) / 2].x) + (c[(l + r) / 2].y) * (c[(l + r) / 2].y));
  14.     while (l <= r)
  15.     {
  16.         while (sqrt((c[l].x) * (c[l].x) + (c[l].y) * (c[l].y)) < piv)
  17.             l++;
  18.         while (sqrt((c[r].x) * (c[r].x) + (c[r].y) * (c[r].y)) > piv)
  19.             r--;
  20.         if (l <= r)
  21.         {
  22.             Coordinates temp;
  23.             temp.x = c[l].x;
  24.             temp.y = c[l].y;
  25.             c[l].x = c[r].x;
  26.             c[l].y = c[r].y;
  27.             c[r].x = temp.x;
  28.             c[r].y = temp.y;
  29.             l++;
  30.             r--;
  31.         }
  32.     }
  33.     if (b < r)
  34.         qsort(c, b, r);
  35.     if (e > l)
  36.         qsort(c, l, e);
  37. }
  38. int main()
  39. {
  40.     int t, x, y, rx, ry, n = 0;
  41.     cin >> t;
  42.     string s = "", res = "";
  43.     Coordinates* c = nullptr;
  44.     int j;
  45.     while (t-- > 0)
  46.     {
  47.         cin >> n;
  48.         c = new Coordinates[n];
  49.         for (int i = 0; i < n; i++)
  50.         {
  51.             cin >> c[i].x >> c[i].y;
  52.         }
  53.         x = y = 0;
  54.         qsort(c, 0, n - 1);
  55.         for (j = 0; j < n; j++)
  56.         {
  57.             if (x <= c[j].x && y <= c[j].y)
  58.             {
  59.                 rx = c[j].x - x;
  60.                 ry = c[j].y - y;
  61.                 if (rx == ry)
  62.                 {
  63.                     for (int i = 0; i < rx; i++)
  64.                         s += 'R';
  65.                     for (int i = 0; i < rx; i++)
  66.                         s += 'U';
  67.                 }
  68.                 else
  69.                 {
  70.                     if (rx < ry)
  71.                     {
  72.                         if (rx == 0)
  73.                         {
  74.                             for (int i = 0; i < ry; i++)
  75.                                 s += 'U';
  76.                         }
  77.                         else
  78.                         {
  79.                             for (int i = 0; i < rx; i++)
  80.                                 s += 'R';
  81.                             for (int i = 0; i < ry; i++)
  82.                                 s += 'U';
  83.                         }
  84.                     }
  85.                     else
  86.                     {  
  87.                         if (ry == 0)
  88.                             for (int i = 0; i < rx; i++)
  89.                                 s += 'R';
  90.                         else
  91.                         {
  92.                             for (int i = 0; i < rx; i++)
  93.                                 s += 'R';
  94.                             for (int i = 0; i < ry; i++)
  95.                                 s += 'U';
  96.                         }
  97.                     }
  98.                 }
  99.                 x = c[j].x;
  100.                 y = c[j].y;
  101.             }
  102.             else
  103.             {
  104.                 s = "";
  105.                 res = res + "NO ";
  106.                 //cout << no << "\n";
  107.                 break;
  108.             }
  109.         }
  110.         if (j == n)
  111.         {
  112.             res += "YES " + s + " ";
  113.             //cout << yes << "\n";
  114.             //cout << s << "\n";
  115.             s = "";
  116.         }
  117.         delete[]c;
  118.     }
  119.     for (int i = 0; i < res.length(); i++)
  120.     {
  121.         if (res[i] == ' ')
  122.             cout << "\n";
  123.         else cout << res[i];
  124.     }
  125.  
  126.     return 0;
  127. }
RAW Paste Data