#line 1 "main.cpp" #ifdef LOCAL #include #else #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2") #include #define debug(...) ((void)0) #define postprocess(...) ((void)0) #endif #line 1 "library/graph/shortest_path.hpp" #include #include #include #include #include template struct shortest_path { const weight unreachable = std::numeric_limits::max(); shortest_path() : _computed(false) {} shortest_path(const int& n, const int& m = 0) : _n(n), _computed(false) { if (m) _edges.reserve(m); } void set_number(const int& n, const int& m = 0) { _n = n; if (m) _edges.reserve(m); } void add_edge(const int& i, const int& j, const weight& w) { assert(0 <= i && i < _n); assert(0 <= j && j < _n); _edges.emplace_back(i, j, w); } void compute(const int& s) { _s = s; _computed = true; _adj.resize(_n); for (auto&& e : _edges) { auto [u, v, w] = e; _adj[u].emplace_back(v, w); } _dist.resize(_n); std::fill(_dist.begin(), _dist.end(), unreachable); _par.resize(_n); std::fill(_par.begin(), _par.end(), -1); // select best algorithm if (!std::is_integral::value) { _dijkstra(s); return; } for (auto&& [_, __, cost] : _edges) { if (cost >= 2) { _dijkstra(s); return; } } for (auto&& [_, __, cost] : _edges) { if (cost == 0) { _bfs01(s); return; } } _bfs(s); } void clear() { _edges.clear(); _adj.clear(); _dist.clear(); _par.clear(); _computed = false; } int s() { assert(_computed); return _s; } std::vector dist() { assert(_computed); return _dist; } weight dist(const int& t) { assert(_computed); return _dist[t]; } std::vector path(int t) { assert(_computed); assert(0 <= t && t < _n); assert(_dist[t] != unreachable); std::vector ret; while (t != _s) { ret.push_back(t); t = _par[t]; } ret.push_back(_s); std::reverse(ret.begin(), ret.end()); return ret; } private: // input values int _n; int _s; std::vector> _edges; // computed values bool _computed; std::vector>> _adj; std::vector _dist; std::vector _par; void _bfs(const int& s) { std::queue que; que.emplace(s); _dist[s] = 0; while (!que.empty()) { auto v = que.front(); que.pop(); for (auto&& [to, _] : _adj[v]) { if (_dist[to] == unreachable) { _dist[to] = _dist[v] + 1; _par[to] = v; que.emplace(to); } } } while (!que.empty()) que.pop(); } void _bfs01(const int& s) { std::deque que; _dist[s] = 0; que.emplace_back(s); while (!que.empty()) { auto v = que.front(); que.pop_front(); for (auto&& [to, cost] : _adj[v]) { weight d = _dist[v] + cost; if (d < _dist[to]) { _dist[to] = d; _par[to] = v; if (cost) { que.emplace_back(to); } else { que.emplace_front(to); } } } } que.clear(); } void _dijkstra(const int& s) { using que_class = std::pair; std::priority_queue, std::greater> que; _dist[s] = 0; que.emplace(0, s); while (!que.empty()) { auto [d, v] = que.top(); que.pop(); if (_dist[v] != d) continue; for (auto&& [to, cost] : _adj[v]) { if (_dist[to] <= d + cost) continue; _dist[to] = d + cost; _par[to] = v; que.emplace(_dist[to], to); } } while (!que.empty()) que.pop(); } }; #line 12 "main.cpp" using namespace std; using ll = long long; using ld = long double; void solve([[maybe_unused]] int test) { ll N, K; cin >> N >> K; const int s = 0; const int g = 1; ll x[N + 2], y[N + 2]; for (int i = 0; i < N + 2; i++) { cin >> x[i] >> y[i]; } ll imin = 0; ll imax = 3e5; auto dist = [&](int i, int j) { return abs(x[i] - x[j]) + abs(y[i] - y[j]); }; auto eval = [&](ll P) -> bool { shortest_path sp(N + 2); for (int i = 0; i < N + 2; i++) { for (int j = 0; j < N + 2; j++) { sp.add_edge(i, j, (dist(i, j) - 1) / P); sp.add_edge(j, i, (dist(j, i) - 1) / P); } } sp.compute(s); bool ret = sp.dist(g) != sp.unreachable && sp.dist(g) <= K; sp.clear(); return ret; }; while (imax - imin > 1) { ll imid = (imin + imax) / 2; (eval(imid) ? imax : imin) = imid; } cout << imax << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(i); } postprocess(); }