#include #include #include #include #include #include #include #include #include #include #include using namespace std; auto now() { return chrono::high_resolution_clock::now(); } using TP = decltype(now()); // time point auto duration(TP t1, TP t2) { return chrono::duration_cast(t2 - t1).count(); } struct P { int x, y; }; int dist(P &l, P &r) { return (l.x - r.x) * (l.x - r.x) + (l.y - r.y) * (l.y - r.y); } struct D { int b, r, dist; bool operator<(const D &x) { return tie(dist, b, r) < tie(x.dist, x.b, x.r); } }; array, 500> adj; int n, b, r; bool random_try(set poss, int dist) { int chosen = 0; while(!poss.empty()) { if(++chosen == n) return true; int x = rand() % poss.size(); auto it = poss.begin(); while(x--) it = next(it); int i = *it; poss.erase(it); // remove neighbours of i if(i < b) { for(int j = b; j < b + r; ++j) if(adj[i][j]) poss.erase(j); } else for(int j = 0; j < b; ++j) if(adj[j][i]) poss.erase(j); } return false; } int main() { auto start = now(); srand(1234); cin >> n >> b >> r; vector

bs(b), rs(r); for(auto &p : bs) cin >> p.x >> p.y; for(auto &p : rs) cin >> p.x >> p.y; vector dists; dists.reserve(b * r); for(int i = 0; i < b; ++i) for(int j = 0; j < r; ++j) dists.push_back({i, b + j, dist(bs[i], rs[j])}); sort(dists.begin(), dists.end()); // auto new_end = unique(dists.begin(), dists.end()); // dists.erase(new_end, dists.end()); // binary search (using iterators :D) the right distance auto be = dists.begin(), e = dists.end(); int steps = int(log(dists.size())) + 5; set poss; for(int i = 0; i < b + r; ++i) poss.insert(i); int step = 0; while(be < e) { ++step; auto m = be + (e - be + 1) / 2; for(auto &x : adj) x.reset(); for(auto x = dists.begin(); x != m; ++x) adj[x->b][x->r] = true; bool success = false; while(!success && duration(start, now()) < step * 900 / steps) success = random_try(poss, prev(m)->dist); if(!success) e = m - 1; else be = m; } cout << fixed << setprecision(15) << sqrt(be->dist) << endl; return 0; }