vadimk772336

Untitled

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