Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <cmath>
- #include <iomanip>
- struct dot
- {
- int x;
- int y;
- double center;
- };
- void simpleSort(dot* dots, int l, int r)
- {
- dot buff;
- int j;
- for (int i = l + 1; i < r + 1; ++i)
- {
- j = i;
- while (j > l && dots[j - 1].center > dots[j].center)
- {
- buff = dots[j - 1];
- dots[j - 1] = dots[j];
- dots[j] = buff;
- j--;
- }
- }
- }
- void merge(dot* dots, int l, int mid, int r)
- {
- int ls = 0, rs = 0;
- dot result[r - l + 1];
- {
- while ((l + ls < mid + 1) && (mid + rs < r))
- {
- if (dots[l + ls].center < dots[mid + rs + 1].center)
- {
- result[ls + rs] = dots[l + ls];
- ls++;
- }
- else
- {
- result[ls + rs] = dots[mid + 1 + rs];
- rs++;
- }
- }
- }
- }
- void mergeSort(dot* dots, int l, int r)
- {
- if (r - l <= 1)
- return;
- if ((r - l) < 12)
- {
- simpleSort(dots, l, r);
- return;
- }
- int mid = (l + r) / 2;
- mergeSort(dots, l, mid);
- mergeSort(dots, mid + 1, r);
- merge(dots, l, mid, r);
- }
- bool is_contain_k(double radius, dot* dots, int n, int k)
- {
- std::queue<int> dots_in_disk;
- int count;
- double center;
- double x_, diff;
- double left;
- int centers[n];
- for (int i = 0; i < n; ++i)
- {
- center = -5000;
- if ((radius * radius - dots[i].y * dots[i].y) >= 0)
- {
- x_ = sqrt(radius * radius - dots[i].y * dots[i].y) + center;
- diff = dots[i].x - x_;
- center += diff;
- dots[i].center = center;
- }
- else
- {
- dots[i].center = 5000;
- }
- }
- mergeSort(dots, 0, n - 1);
- dots_in_disk.push(0);
- count = 1;
- double x, y;
- for (int i = 1; i < n; ++i)
- {
- if (dots[i].center < 1000 + radius)
- {
- if (dots[i].center == dots[i - 1].center)
- {
- count++;
- if (count == k)
- return true;
- }
- else
- {
- diff = dots[i].center - center;
- left = center - radius;
- x = dots[dots_in_disk.front()].x;
- y = dots[dots_in_disk.front()].y;
- double prev_center = dots[dots_in_disk.front()].center;
- while (count > 0
- && ((x - center - diff) * (x - center - diff) + y * y > radius * radius))
- {
- count--;
- dots_in_disk.pop();
- while (count > 0 && prev_center == dots[dots_in_disk.front()].center)
- {
- count--;
- prev_center = dots[dots_in_disk.front()].center;
- dots_in_disk.pop();
- }
- x = dots[dots_in_disk.front()].x;
- y = dots[dots_in_disk.front()].y;
- prev_center == dots[dots_in_disk.front()].center;
- if (count == k)
- return true;
- }
- center += diff;
- left += diff;
- dots_in_disk.push(i);
- count++;
- if (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-6)
- {
- 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()
- {
- 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;
- }
- if (k == 1)
- {
- int min_y = 1001;
- for (int i = 0; i < n; ++i)
- {
- if (dots[i].y < min_y)
- min_y = dots[i].y;
- }
- std::cout << std::setprecision(7) << min_y;
- return 0;
- }
- double res = binary_search(dots, n, k);
- std::cout << std::setprecision(7) << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment