Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef double ld;
- mt19937 rnd((0xb22 + 3503 - 0x17ed));
- #define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
- const int M = 5e4 + (0xfd2 + 5479 - 0x244a);
- const int X = (int)(1e8) + (0x50b + 154 - 0x4b6);
- const int T = ((0xe40 + 2177 - 0x16c0) << (0x1bfc + 2296 - 0x24e3)) + (0x1e83 + 1995 - 0x255f);
- const ld pi = acos((ld)-1.0);
- int n, l, k, bd, x[M], y[M];
- int idx[M], sz_idx;
- int divide(int a, int b) {
- if (a >= (0xcd5 + 3940 - 0x1c39) || a % b == (0x1548 + 550 - 0x176e)) {
- return a / b;
- }
- return -(abs(a) / b) - (0xbc5 + 4900 - 0x1ee8);
- }
- class Hasher {
- public:
- size_t operator()(const pair<int, int>& key) const {
- return ((ll)(key.first + X) << 30LL) + (ll)key.second;
- }
- };
- struct helper {
- int R = (0x863 + 3196 - 0x14df);
- int l = (0xd44 + 578 - 0xf86);
- int r = (0x1d1b + 222 - 0x1df9);
- unordered_map<pair<int, int>, unordered_set<int>, Hasher> in;
- template <typename P>
- void upload(int x, int y, P pred) {
- int xi = divide(x, R);
- int yi = divide(y, R);
- for (int dx = -(0x1a04 + 1493 - 0x1fd8); dx <= (0x1551 + 3334 - 0x2256); dx++) {
- for (int dy = -(0x310 + 9179 - 0x26ea); dy <= (0x1178 + 5091 - 0x255a); dy++) {
- auto it = in.find(make_pair(xi + dx, yi + dy));
- if (it != in.end()) {
- for (int i : it->second) {
- if (pred(i)) {
- idx[sz_idx++] = i;
- }
- }
- }
- }
- }
- }
- void add(int i) {
- int xi = divide(::x[i], R);
- int yi = divide(::y[i], R);
- in[make_pair(xi, yi)].insert(i);
- }
- void del(int i) {
- int xi = divide(::x[i], R);
- int yi = divide(::y[i], R);
- in[make_pair(xi, yi)].erase(i);
- }
- void remake(ld new_r) {
- R = ceil(new_r) + (0x356 + 505 - 0x54e);
- in.clear();
- in.reserve(sz_idx * (0x8fd + 2339 - 0x121e));
- for (int i = l; i < r; i++) {
- add(i);
- }
- }
- void move_left() {
- del(l);
- l++;
- }
- void move_right() {
- add(r);
- r++;
- }
- };
- ld dist(int i, int j) {
- return hypot(x[j] - x[i], y[j] - y[i]);
- }
- ld angle(int i, int j) {
- return atan2(y[j] - y[i], x[j] - x[i]);
- }
- int tree[T], add[T];
- void build(int i, int l, int r) {
- tree[i] = (0x19f1 + 1358 - 0x1f3f);
- add[i] = (0x6cd + 570 - 0x907);
- if (r - l == (0x236 + 2712 - 0xccd)) {
- return;
- }
- int mid = (l + r) / (0x15bc + 2692 - 0x203e);
- build((0x449 + 4417 - 0x1588) * i + (0xb19 + 1749 - 0x11ed), l, mid);
- build((0xc19 + 2861 - 0x1744) * i + (0x13bb + 24 - 0x13d1), mid, r);
- }
- inline void push(int i, int l, int r) {
- tree[i] += add[i];
- if (r - l > (0xa94 + 5153 - 0x1eb4)) {
- add[(0x6a6 + 1030 - 0xaaa) * i + (0xbf4 + 731 - 0xece)] += add[i];
- add[(0x1245 + 517 - 0x1448) * i + (0x66 + 157 - 0x101)] += add[i];
- }
- add[i] = (0xbb + 1506 - 0x69d);
- }
- void upd(int i, int l, int r, int ql, int qr, int x) {
- push(i, l, r);
- if (r <= ql || qr <= l) {
- return;
- }
- if (ql <= l && r <= qr) {
- add[i] += x;
- push(i, l, r);
- return;
- }
- int mid = (l + r) / (0x2d6 + 7883 - 0x219f);
- upd((0x1706 + 1547 - 0x1d0f) * i + (0x1c89 + 1860 - 0x23cc), l, mid, ql, qr, x);
- upd((0x1a41 + 1586 - 0x2071) * i + (0xa02 + 5922 - 0x2122), mid, r, ql, qr, x);
- tree[i] = max(tree[(0xf58 + 3561 - 0x1d3f) * i + (0x580 + 7024 - 0x20ef)], tree[(0x398 + 4706 - 0x15f8) * i + (0x8e9 + 519 - 0xaee)]);
- }
- void clear(int i, int l, int r) {
- push(i, l, r);
- if (tree[i] == (0x23e6 + 401 - 0x2577)) {
- return;
- }
- tree[i] = (0x170f + 2868 - 0x2243);
- if (r - l > (0x3c0 + 3856 - 0x12cf)) {
- int mid = (l + r) / (0xcb5 + 4358 - 0x1db9);
- clear((0xc20 + 4345 - 0x1d17) * i + (0x1ed7 + 1621 - 0x252b), l, mid);
- clear((0x145c + 2040 - 0x1c52) * i + (0x173 + 8795 - 0x23cc), mid, r);
- }
- }
- int s[M], cnt;
- vector<pair<ld, int>> events;
- bool check(int p, ld t) {
- if (sz_idx < k - (0x130 + 1117 - 0x58c)) {
- return false;
- }
- bool ans = false;
- events.clear();
- events.reserve(sz_idx * (0xaf7 + 5146 - 0x1f0f));
- cnt = (0xa12 + 7071 - 0x25b1);
- for (int ii = (0xe49 + 3408 - 0x1b99); ii < sz_idx; ii++) {
- int i = idx[ii];
- ld d = dist(p, i);
- if (d > (0x1c2f + 757 - 0x1f22) * t) {
- continue;
- }
- ld a = angle(p, i);
- ld len = acos(min((ld)1.0, d / ((0x135c + 792 - 0x1672) * t)));
- ld lg = a - len;
- ld rg = a + len;
- if (lg < -pi) {
- lg += (0x1c61 + 1500 - 0x223b) * pi;
- }
- if (rg > pi) {
- rg -= (0x8c3 + 4775 - 0x1b68) * pi;
- }
- events.emplace_back(lg, -(0x368 + 554 - 0x591) - i);
- events.emplace_back(rg, (0x276 + 1209 - 0x72e) + i);
- if (lg > rg) {
- upd((0x1420 + 1674 - 0x1aaa), (0x791 + 6525 - 0x210e), bd, max((0x155b + 2615 - 0x1f92), i - l + (0x11f4 + 1468 - 0x17af)),
- min(bd, i + (0x168d + 1769 - 0x1d75)), (0x161 + 2936 - 0xcd8));
- s[cnt++] = i;
- if (tree[(0x5a + 3054 - 0xc48)] >= k - (0x13aa + 1650 - 0x1a1b)) {
- ans = true;
- }
- }
- }
- if (!ans) {
- sort(events.begin(), events.end());
- for (const auto& t : events) {
- if (t.second < (0x14d8 + 2966 - 0x206e)) {
- int i = -t.second - (0x303 + 5880 - 0x19fa);
- upd((0x1027 + 2204 - 0x18c3), (0xe81 + 1999 - 0x1650), bd, max((0x5c7 + 3742 - 0x1465), i - l + (0xc62 + 6384 - 0x2551)),
- min(bd, i + (0x17ab + 2932 - 0x231e)), (0x86d + 615 - 0xad3));
- } else {
- int i = t.second - (0x99b + 6597 - 0x235f);
- upd((0x50c + 1593 - 0xb45), (0x4ba + 627 - 0x72d), bd, max((0x18ed + 3601 - 0x26fe), i - l + (0x5a6 + 7210 - 0x21cf)),
- min(bd, i + (0x1973 + 2355 - 0x22a5)), -(0x19 + 6619 - 0x19f3));
- }
- if (tree[(0x1065 + 4109 - 0x2072)] >= k - (0x6aa + 1952 - 0xe49)) {
- ans = true;
- }
- }
- }
- for (int i = (0x9d + 6142 - 0x189b); i < cnt; i++) {
- upd((0x8c8 + 7023 - 0x2437), (0x10ab + 676 - 0x134f), bd, max((0x1182 + 4113 - 0x2193), s[i] - l + (0xc97 + 5635 - 0x2299)),
- min(bd, s[i] + (0x7fb + 3819 - 0x16e5)), -(0x1220 + 194 - 0x12e1));
- }
- return ans;
- }
- ld func(helper& hl, helper& hr, int p, ld pa) {
- auto is_good = [&](int i) { return dist(p, i) <= (0xba6 + 2701 - 0x1631) * pa; };
- sz_idx = (0x1862 + 1121 - 0x1cc3);
- hl.upload(x[p], y[p], is_good);
- hr.upload(x[p], y[p], is_good);
- if (!check(p, pa)) {
- return pa;
- }
- ld lg = (0xef0 + 2425 - 0x1869);
- ld rg = pa;
- for (int i = (0xd3f + 4504 - 0x1ed7); i < (0x1550 + 2051 - 0x1d0d); i++) {
- ld mid = (lg + rg) / (0x47c + 3508 - 0x122e);
- if (check(p, mid)) {
- rg = mid;
- } else {
- lg = mid;
- }
- }
- hl.remake((0xa06 + 6822 - 0x24aa) * rg);
- hr.remake((0x113f + 4448 - 0x229d) * rg);
- return rg;
- }
- void solve() {
- memset(x, (0x9b2 + 5642 - 0x1fbc), sizeof(x));
- memset(y, (0x21db + 458 - 0x23a5), sizeof(y));
- cin >> n >> l >> k;
- for (int i = (0xe06 + 1862 - 0x154c); i < n; i++) {
- cin >> x[i] >> y[i];
- }
- bd = n - l + (0x4e8 + 2764 - 0xfb3);
- int s = sqrt((ld)(l - (0x1ad7 + 1825 - 0x21f7)) / (k - (0x943 + 3926 - 0x1898)));
- ld ans = ((1e8 / s) * sqrt((0x16a0 + 2946 - 0x2220))) + (0x213 + 9393 - 0x26c3);
- helper hl, hr;
- hl.remake((0x85d + 670 - 0xaf9) * ans);
- hr.remake((0xa15 + 5636 - 0x2017) * ans);
- for (int i = (0xf51 + 4628 - 0x2165); i < l; i++) {
- hr.move_right();
- }
- build((0xa2d + 1407 - 0xfac), (0xf11 + 5021 - 0x22ae), n);
- for (int i = (0x89 + 8385 - 0x214a); i < n; i++) {
- hr.move_left();
- ans = min(ans, func(hl, hr, i, ans));
- if (i + (0x1491 + 2652 - 0x1eec) == n) {
- break;
- }
- if (i + l < n) {
- hr.move_right();
- }
- if (i - l + (0x8fc + 2853 - 0x1420) >= (0x5d9 + 2288 - 0xec9)) {
- hl.move_left();
- }
- hl.move_right();
- }
- cout << ans << "\n";
- }
- int main() {
- cout << fixed << setprecision((0x2170 + 228 - 0x2240));
- int t;
- cin >> t;
- while (t--) {
- solve();
- }
- return (0x39a + 2521 - 0xd73);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement