#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); typedef long long ll; int getSource() { return 0; } int getArmy(int n) { return n + 1; } int getBase(int N, int m) { return getArmy(N) + m; } int getSink(int N, int M) { return getBase(N, M); } struct Edge { int n, m; double r; bool operator<(const Edge& rh) const{ return r < rh.r; } }; typedef vector Array; typedef vector Matrix; int maxFlow(Matrix& capacity, int s, int t) { const int n = capacity.size(); int result = 0; for (;;){ vector open; open.push_back(s); vector prev(n, -1); while (!open.empty() && prev[t] == -1){ const int from = open.back(); open.pop_back(); for (int to = 0; to < n; ++to){ if (prev[to] >= 0 || !capacity[from][to]){ continue; } prev[to] = from; open.push_back(to); } } if (prev[t] == -1){ break; } vector path; path.push_back(t); int flow = INT_MAX; while (path.back() != s){ flow = min(flow, capacity[prev[path.back()]][path.back()]); path.push_back(prev[path.back()]); } for (int i = 0; i < path.size() - 1; ++i){ capacity[path[i + 1]][path[i]] -= flow; capacity[path[i]][path[i + 1]] += flow; } result += flow; } return result; } int main() { for (int N, M; cin >> N >> M;) { vector xs; vector ys; vector vs; for (int n = 0; n < N; ++n){ int x, y, v; cin >> x >> y >> v; xs.push_back(x); ys.push_back(y); vs.push_back(v); } vector edges; for (int m = 0; m < M; ++m){ int x, y; cin >> x >> y; for (int n = 0; n < N; ++n){ Edge e; e.n = n; e.m = m; e.r = hypot(xs[n] - x, ys[n] - y) / vs[n]; edges.push_back(e); } } sort(edges.begin(), edges.end()); const int size = N + M + 2; Matrix g(size, Array(size)); for (int n = 0; n < N; ++n){ g[getSource()][getArmy(n)] = 1; } for (int m = 0; m < M; ++m){ g[getBase(N, m)][getSink(N, M)] = 1; } int totalFlow = 0; vector::iterator it = edges.begin(); do { const Edge& edge = *it++; g[getArmy(edge.n)][getBase(N, edge.m)] = 1; totalFlow += maxFlow(g, getSource(), getSink(N, M)); } while (totalFlow < M); --it; printf("%.20lf\n", it->r); } }