#include #include #include #include #include using namespace std; const int MAXK=1e5, MAXN=1e5, MAXD=1e9; double s[MAXK]; pair c[MAXN]; pair pos[MAXK]; vector ans; vector > currPos; vector > workers; void ClearData() { workers.clear(); currPos.clear(); ans.clear(); } pair GetNaiveResult(int p, double t, int cIdx, int n, int k, double cost) { if(cIdx==n) { return {p, t}; } double minCost=sqrt(2)*10*MAXD; int minIdx=-1; for(int i=0; icost) { if(p(currPos[minIdx]), c[cIdx].first, c[cIdx].second); t+=minCost; ans.push_back(workers[minIdx].second); } return GetNaiveResult(p, t, cIdx+1, n, k, cost); } void Solve(int n, int k) { for(int i=0; ioffset) { double mid=l+(r-l)/2; int p; double t; ClearData(); tie(p, t)=GetNaiveResult(0, 0, 0, n, k, mid); if(p<=k) { if(p==k) { ans=t; } r=mid; } else { l=mid; } } ClearData(); GetNaiveResult(0, 0, 0, n, k, ans); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); freopen("runners.in", "r", stdin); freopen("runners.out", "w", stdout); int n, k; cin >> n >> k; for(int i=0; i> s[i]; } for(int i=0; i> c[i].first >> c[i].second; } Solve(n, k); for(int i=0; i