#include // #include #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define INF 2000000000000000000 #define ll long long #define ull unsigned long long #define ld long double #define pll pair using namespace std; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> N >> K; vector points(N + 2); for (ll i = 0; i < N + 2; ++i) { cin >> points.at(i).first >> points.at(i).second; } ll l = 0, r = 200010; //log(10 ^ 5) ≒ 20 while (l + 1 < r) { ll m = (l + r) / 2; vector dp(N + 2, INF); dp.at(0) = 0; priority_queue, greater> q; q.push({0, 0}); while (!q.empty()) { ll now = q.top().second, d = q.top().first; q.pop(); if (d > dp.at(now)) { continue; } for (ll i = 0; i < N + 2; ++i) { ll nd = d + (abs(points.at(now).first - points.at(i).first) + abs(points.at(now).second - points.at(i).second) - 1) / m; if (dp.at(i) > nd) { dp.at(i) = nd; q.push({nd, i}); } } } // cout << "dp" << m << "\n"; // for (ll i = 0; i < N + 2; ++i) { // cout << dp.at(i) << " "; // } // cout << "\n"; if (dp.at(1) <= K) { r = m; } else { l = m; } } cout << r << "\n"; }