Proficient.
Put your skills to the test.

Problem summary

Assign N sheep to M shelters, each holding at most K sheep. All sheep move simultaneously at unit speed along straight lines. Minimize the time until all sheep are sheltered.

Constraints

1≤N,M,K≤500; coordinates in [−1000,1000]; N≤MK, so a feasible assignment exists.

Worked example

An independently prepared example for this explanation.

5 3 2
2 13
9 6
4 8
13 7
11 3
2 11
10 6
4 12

7.810250

Solution analysis

1. For a candidate squared distance D, join each sheep to every shelter at squared distance at most D. Add a source-to-sheep edge of capacity 1 and a shelter-to-sink edge of capacity K. All sheep fit exactly when maximum flow is N.
2. The answer is one of the NM pairwise squared distances. Sort the distinct values and binary search the first feasible one. This avoids floating-point decisions; only the final square root requires real arithmetic.
3. In the sample, assigning (9,6) to (4,12) requires distance √61≈7.810250. Sending it to the closer (10,6) would overload that shelter in the proposed optimum, demonstrating why independent nearest-shelter choices do not suffice.

Why it works

Integral flows correspond bijectively to assignments satisfying shelter capacities and the distance threshold. Adding allowed edges can only preserve or improve feasibility, so the predicate is monotone. Every assignment has a largest used pairwise distance; binary search finds the least feasible one, whose square root is the optimal time.

Watch out. Capacity K belongs on shelter-to-sink edges. Compare squared integer distances, and preserve coincident points as separate sheep or shelters.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
#include<cmath>
#include<iomanip>
// Algorithm: For a candidate squared distance D, join each sheep to every shelter at squared
// distance at most D.
using namespace std;
struct Edge{
    int to;
    int reverse;
    int capacity;
};
struct Dinic{
    vector<vector<Edge>>graph;
    vector<int>level;
    vector<int>nextEdge;
    explicit Dinic(int vertices):graph(vertices),level(vertices),nextEdge(vertices){
    }
    void addEdge(int from,int to,int capacity){
        Edge forward={to,static_cast<int>(graph[to].size()),capacity};
        Edge backward={from,static_cast<int>(graph[from].size()),0};
        graph[from].push_back(forward);
        graph[to].push_back(backward);
    }
    bool buildLevels(int source,int sink){
        fill(level.begin(),level.end(),-1);
        queue<int>pending;
        pending.push(source);
        level[source]=0;
        while(!pending.empty()){
            int vertex=pending.front();
            pending.pop();
            for(const Edge&edge:graph[vertex]){
                if(edge.capacity>0&&level[edge.to]==-1){
                    level[edge.to]=level[vertex]+1;
                    pending.push(edge.to);
                }
            }
        }
        return level[sink]!=-1;
    }
    int send(int vertex,int sink,int amount){
        if(vertex==sink){
            return amount;
        }
        for(int&index=nextEdge[vertex];index<static_cast<int>(graph[vertex].size());index++){
            Edge&edge=graph[vertex][index];
            if(edge.capacity>0&&level[edge.to]==level[vertex]+1){
                int sent=send(edge.to,sink,min(amount,edge.capacity));
                if(sent!=0){
                    edge.capacity-=sent;
                    graph[edge.to][edge.reverse].capacity+=sent;
                    return sent;
                }
            }
        }
        return 0;
    }
    int maximumFlow(int source,int sink){
        int total=0;
        while(buildLevels(source,sink)){
            fill(nextEdge.begin(),nextEdge.end(),0);
            int sent;
            while((sent=send(source,sink,1000000000))!=0){
                total+=sent;
            }
        }
        return total;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int sheepCount,shelterCount,capacity;
    cin>>sheepCount>>shelterCount>>capacity;
    vector<pair<int,int>>sheep(sheepCount),shelters(shelterCount);
    for(auto&point:sheep){
        cin>>point.first>>point.second;
    }
    for(auto&point:shelters){
        cin>>point.first>>point.second;
    }
    vector<vector<int>>squared(sheepCount,vector<int>(shelterCount));
    vector<int>candidates;
    for(int i=0;i<sheepCount;i++){
        for(int j=0;j<shelterCount;j++){
            int dx=sheep[i].first-shelters[j].first;
            int dy=sheep[i].second-shelters[j].second;
            squared[i][j]=dx*dx+dy*dy;
            candidates.push_back(squared[i][j]);
        }
    }
    sort(candidates.begin(),candidates.end());
    candidates.erase(unique(candidates.begin(),candidates.end()),candidates.end());
    auto feasible=[&](int threshold){
        int source=sheepCount+shelterCount;
        int sink=source+1;
        Dinic network(sink+1);
        for(int i=0;i<sheepCount;i++){
            network.addEdge(source,i,1);
            for(int j=0;j<shelterCount;j++){
                if(squared[i][j]<=threshold){
                    network.addEdge(i,sheepCount+j,1);
                }
            }
        }
        for(int j=0;j<shelterCount;j++){
            network.addEdge(sheepCount+j,sink,capacity);
        }
        return network.maximumFlow(source,sink)==sheepCount;
    };
    int low=0;
    int high=static_cast<int>(candidates.size())-1;
    while(low<high){
        int middle=(low+high)/2;
        if(feasible(candidates[middle])){
            high=middle;
        }
        else{
            low=middle+1;
        }
    }
    cout<<fixed<<setprecision(6)<<sqrt(static_cast<double>(candidates[low]))<<'\n';
}