vadimk772336

Untitled

Oct 9th, 2021 (edited)
867
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4. #include <iomanip>
  5.  
  6.  
  7. struct dot
  8. {
  9.     int x;
  10.     int y;
  11.     double center;
  12. };
  13.  
  14. void simpleSort(dot* dots, int l, int r)
  15. {
  16.     dot buff;
  17.     int j;
  18.  
  19.     for (int i = l + 1; i < r + 1; ++i)
  20.     {
  21.         j = i;
  22.         while (j > l && dots[j - 1].center > dots[j].center)
  23.         {
  24.             buff = dots[j - 1];
  25.             dots[j - 1] = dots[j];
  26.             dots[j] = buff;
  27.             j--;
  28.         }
  29.     }
  30. }
  31.  
  32. void merge(dot* dots, int l, int mid, int r)
  33. {
  34.     int ls = 0, rs = 0;
  35.     dot result[r - l + 1];
  36.  
  37.     {
  38.         while ((l + ls < mid + 1) && (mid + rs < r))
  39.         {
  40.             if (dots[l + ls].center < dots[mid + rs + 1].center)
  41.             {
  42.                 result[ls + rs] = dots[l + ls];
  43.                 ls++;
  44.             }
  45.             else
  46.             {
  47.                 result[ls + rs] = dots[mid + 1 + rs];
  48.                 rs++;
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. void mergeSort(dot* dots, int l, int r)
  55. {
  56.     if (r - l <= 1)
  57.         return;
  58.  
  59.     if ((r - l) < 12)
  60.     {
  61.         simpleSort(dots, l, r);
  62.         return;
  63.     }
  64.  
  65.     int mid = (l + r) / 2;
  66.     mergeSort(dots, l, mid);
  67.     mergeSort(dots, mid + 1, r);
  68.     merge(dots, l, mid, r);
  69. }
  70.  
  71.  
  72. bool is_contain_k(double radius, dot* dots, int n, int k)
  73. {
  74.  
  75.     std::queue<int> dots_in_disk;
  76.     int count;
  77.     double center;
  78.     double x_, diff;
  79.     double left;
  80.  
  81.     int centers[n];
  82.     for (int i = 0; i < n; ++i)
  83.     {
  84.         center = -5000;
  85.         if ((radius * radius - dots[i].y * dots[i].y) >= 0)
  86.         {
  87.  
  88.             x_ = sqrt(radius * radius - dots[i].y * dots[i].y) + center;
  89.             diff = dots[i].x - x_;
  90.             center += diff;
  91.             dots[i].center = center;
  92.         }
  93.         else
  94.         {
  95.             dots[i].center = 5000;
  96.         }
  97.     }
  98.     mergeSort(dots, 0, n - 1);
  99.  
  100.  
  101.     dots_in_disk.push(0);
  102.     count = 1;
  103.     double x, y;
  104.     for (int i = 1; i < n; ++i)
  105.     {
  106.         if (dots[i].center < 1000 + radius)
  107.         {
  108.             if (dots[i].center == dots[i - 1].center)
  109.             {
  110.                 count++;
  111.                 if (count == k)
  112.                     return true;
  113.             }
  114.             else
  115.             {
  116.                 diff = dots[i].center - center;
  117.                 left = center - radius;
  118.                 x = dots[dots_in_disk.front()].x;
  119.                 y = dots[dots_in_disk.front()].y;
  120.                 double prev_center = dots[dots_in_disk.front()].center;
  121.  
  122.                 while (count > 0
  123.                     && ((x - center - diff) * (x - center - diff) + y * y > radius * radius))
  124.                 {
  125.                     count--;
  126.                     dots_in_disk.pop();
  127.                     while (count > 0 && prev_center == dots[dots_in_disk.front()].center)
  128.                     {
  129.                         count--;
  130.                         prev_center = dots[dots_in_disk.front()].center;
  131.                         dots_in_disk.pop();
  132.                     }
  133.  
  134.                     x = dots[dots_in_disk.front()].x;
  135.                     y = dots[dots_in_disk.front()].y;
  136.                     prev_center == dots[dots_in_disk.front()].center;
  137.                     if (count == k)
  138.                         return true;
  139.                 }
  140.                 center += diff;
  141.                 left += diff;
  142.                 dots_in_disk.push(i);
  143.                 count++;
  144.  
  145.                 if (count == k)
  146.                 {
  147.  
  148.                     return true;
  149.                 }
  150.             }
  151.         }
  152.     }
  153.     return false;
  154. }
  155.  
  156. double binary_search(dot* dots, int n, int k)
  157. {
  158.     double max_r = 1420;
  159.     double min_r = 0;
  160.     double radius;
  161.  
  162.     while (max_r - min_r > 1e-6)
  163.     {
  164.         radius = (max_r + min_r) / 2;
  165.         if (is_contain_k(radius, dots, n, k))
  166.         {
  167.             max_r = radius;
  168.         }
  169.         else
  170.         {
  171.             min_r = radius;
  172.         }
  173.     }
  174.  
  175.     return max_r;
  176. }
  177.  
  178. int main()
  179. {
  180.     int n, k;
  181.  
  182.     std::cin >> n;
  183.     std::cin >> k;
  184.     dot dots[n] = {};
  185.     for (int i = 0; i < n; ++i)
  186.     {
  187.         std::cin >> dots[i].x;
  188.         std::cin >> dots[i].y;
  189.     }
  190.  
  191.  
  192.     if (k == 1)
  193.     {
  194.         int min_y = 1001;
  195.         for (int i = 0; i < n; ++i)
  196.         {
  197.             if (dots[i].y < min_y)
  198.                 min_y = dots[i].y;
  199.         }
  200.         std::cout << std::setprecision(7) << min_y;
  201.         return 0;
  202.     }
  203.  
  204.     double res = binary_search(dots, n, k);
  205.     std::cout << std::setprecision(7) << res;
  206.  
  207.     return 0;
  208. }
  209.  
Advertisement
Add Comment
Please, Sign In to add comment