#include using namespace std; using vi = vector; constexpr int INF = 1e9; // MAX FLOW using F = int; using W = int; // types for flow and weight/cost struct S{ const int v; // neighbour const int r; // index of the reverse edge F f; // current flow const F cap; // capacity const W cost; // unit cost S(int v, int ri, F c, W cost = 0) : v(v), r(ri), f(0), cap(c), cost(cost) {} }; struct FlowGraph : vector> { FlowGraph(size_t n) : vector>(n) {} void add_edge(int u, int v, F c, W cost = 0){ auto &t = *this; t[u].emplace_back(v, t[v].size(), c, cost); t[v].emplace_back(u, t[u].size()-1, 0, -cost); } }; struct Dinic{ FlowGraph &edges; int V,s,t; vi l; vector::iterator> its; // levels and iterators Dinic(FlowGraph &edges, int s, int t) : edges(edges), V(edges.size()), s(s), t(t), l(V,-1), its(V) {} int augment(int u, F c) { // we reuse the same iterators if (u == t) return c; for(auto &i = its[u]; i != edges[u].end(); i++){ auto &e = *i; if (e.cap > e.f && l[u] < l[e.v]) { auto d = augment(e.v, min(c, e.cap - e.f)); if (d > 0) { e.f += d; edges[e.v][e.r].f -= d; return d; } } } return 0; } int run() { int flow = 0, f; while(true) { fill(l.begin(), l.end(),-1); l[s]=0; // recalculate the layers queue q; q.push(s); while(!q.empty()){ auto u = q.front(); q.pop(); for(auto &&e : edges[u]) if(e.cap > e.f && l[e.v]<0) l[e.v] = l[u]+1, q.push(e.v); } if (l[t] < 0) return flow; for (int u = 0; u < V; ++u) its[u] = edges[u].begin(); while ((f = augment(s, INF)) > 0) flow += f; } } }; //-MAX FLOW int lsq(int x1, int y1, int x2, int y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } struct BR { int b, r, dsq; }; int main() { int N, B, R; cin >> N >> B >> R; vi Bx(B, 0), By(B, 0), Rx(R, 0), Ry(R, 0); for (int i = 0; i < B; ++i) cin >> Bx[i] >> By[i]; for (int i = 0; i < R; ++i) cin >> Rx[i] >> Ry[i]; vector
brs; for (int i = 0; i < B; ++i) for (int j = 0; j < R; ++j) brs.push_back(BR{i, j, lsq(Bx[i], By[i], Rx[j], Ry[j])}); sort(brs.begin(), brs.end(), [](const BR &l, const BR &r) { return l.dsq < r.dsq; }); FlowGraph fg(B + R + 2); int SOURCE = B + R, SINK = B + R + 1; for (int i = 0; i < B; ++i) fg.add_edge(SOURCE, i, 1); for (int i = 0; i < R; ++i) fg.add_edge(B + i, SINK, 1); N = B + R - N; Dinic dn(fg, SOURCE, SINK); for (size_t l = 0, r = 0; l < brs.size(); l = r) { while (r < brs.size() && brs[l].dsq == brs[r].dsq) ++r; for (size_t i = l; i < r; ++i) fg.add_edge(brs[i].b, B + brs[i].r, 1); N -= dn.run(); if (N < 0) { printf("%.10lf\n", sqrt(double(brs[l].dsq))); return 0; } } printf("%.10lf\n", sqrt(double(brs.back().dsq))); }