Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <iomanip>
- struct dot
- {
- int x;
- int y;
- };
- struct center_status
- {
- double x;
- int status;
- };
- void simpleSort(center_status* states, int l, int r)
- {
- center_status buff;
- int j;
- for (int i = l + 1; i < r + 1; ++i)
- {
- j = i;
- while (j > l && states[j - 1].x > states[j].x)
- {
- buff = states[j - 1];
- states[j - 1] = states[j];
- states[j] = buff;
- j--;
- }
- }
- }
- void merge(center_status* states, int l, int mid, int r)
- {
- int ls = 0, rs = 0;
- center_status result[r - l + 1];
- while ((l + ls < mid + 1) && (mid + rs < r))
- {
- if (states[l + ls].x < states[mid + rs + 1].x)
- {
- result[ls + rs] = states[l + ls];
- ls++;
- }
- else
- {
- result[ls + rs] = states[mid + 1 + rs];
- rs++;
- }
- }
- while (l + ls < mid + 1)
- {
- result[ls + rs] = states[l + ls];
- ls++;
- }
- while (mid + rs < r)
- {
- result[ls + rs] = states[mid + rs + 1];
- rs++;
- }
- for (int i = 0; i < ls + rs; ++i)
- states[l + i] = result[i];
- }
- void mergeSort(center_status* states, int l, int r)
- {
- if (r - l <= 1)
- return;
- if (r - l < 12)
- {
- simpleSort(states, l, r);
- return;
- }
- int mid = (l + r) / 2;
- mergeSort(states, l, mid);
- mergeSort(states, mid + 1, r);
- merge(states, l, mid, r);
- }
- bool is_contain_k(double radius, dot* dots, int n, int k)
- {
- double eps = 1e-6;
- double offset;
- center_status states[2 * n];
- for (int i = 0; i < n; ++i)
- {
- if (std::abs(dots[i].y) < radius)
- {
- offset = sqrt(radius * radius - dots[i].y * dots[i].y);
- states[2 * i].x = dots[i].x - offset - eps * (i + 1);
- states[2 * i].status = 1;
- states[2 * i + 1].x = dots[i].x + offset + eps * (i + 1);
- states[2 * i + 1].status = 0;
- }
- else
- {
- states[2 * i].x = 0;
- states[2 * i].status = 2;
- states[2 * i + 1].x = 0;
- states[2 * i + 1].status = 2;
- }
- }
- mergeSort(states, 0, 2 * n - 1);
- int curr_count = 0;
- int max_count = 0;
- for (int i = 0; i < 2 * n; ++i)
- {
- if (states[i].status == 1)
- {
- curr_count++;
- if (curr_count > max_count)
- max_count = curr_count;
- }
- if (states[i].status == 0)
- {
- curr_count--;
- }
- }
- if (max_count >= k)
- return true;
- return false;
- }
- double binary_search(dot* dots, int n, int k)
- {
- double max_r = 1420;
- double min_r = 0;
- double radius;
- while (max_r - min_r > 1e-4)
- {
- radius = (max_r + min_r) / 2;
- if (is_contain_k(radius, dots, n, k))
- max_r = radius;
- else
- min_r = radius;
- }
- return max_r;
- }
- int main()
- {
- std::cout.setf(std::ios::fixed);
- std::cout.precision(6);
- int n, k;
- std::cin >> n;
- std::cin >> k;
- dot dots[n] = {};
- for (int i = 0; i < n; ++i)
- {
- std::cin >> dots[i].x;
- std::cin >> dots[i].y;
- }
- double res = binary_search(dots, n, k);
- std::cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment