Expert.
Put your skills to the test.

Problem summary

Place K guards in the plane to reduce the sum, over N given points, of the Euclidean distance to their nearest guard. This is a scored optimization task: a valid output need not be globally optimal.

Source clarification. The original task explicitly permits nonoptimal output and awards a quality-dependent score.

Constraints

1≤K<N≤1000;K≤100;0≤coordinates≤10000.

Worked example

An independently prepared worked example; constructive outputs may have other valid forms.

4 2
0 0
0 0
10 0
10 0

0.000000 0.000000
10.000000 0.000000

Solution analysis

1. This objective uses distances, not squared distances. For a fixed cluster, its best guard is a geometric median, not generally its arithmetic mean. Globally choosing both clusters and guard positions is difficult; the source explicitly awards a score according to objective quality. The published scoring formula is round(min(1,author_score/your_score)^2 * test_score); quality depends on the hidden reference score.
2. The program uses three deterministic restarts. Starting with a chosen input point, repeatedly choose the point farthest from its nearest current guard. Then alternate nearest-guard assignment and approximate geometric-median updates using a bounded modified Weiszfeld iteration.
3. If an iterate coincides with data points, ordinary Weiszfeld division would fail. The modified update counts coincident points and either recognizes a median or blends the noncoincident weighted update with the current point. Keep the best complete arrangement seen, so a later numerical or clustering deterioration cannot replace a better result.
4. For two points at(0,0) and two at(10,0), farthest-first initialization selects exactly those two coordinates. Every point then has distance0 to its closest guard, so the objective0 is globally optimal for this worked example.

Why it works

Every produced center lies in the convex hull of input cluster points, so it is a valid real coordinate. Assignment picks the nearest available guard. The program explicitly evaluates and retains the lowest observed objective across initializations and updates. This proves validity and retention of the best visited result, not global optimality. The task’s score depends on that quality.

Watch out. Do not replace the objective by squared-distance k-means or call arithmetic means exact medians. Handle empty clusters and zero distances. This heuristic has no guaranteed optimum, approximation ratio or full-score claim.

Deterministic bounded geometric-k-median heuristic; no maximum-score guarantee.

#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
struct Point{
    long double x,y;
};
long double squared(Point a,Point b){
    long double dx=a.x-b.x;
    long double dy=a.y-b.y;
    return dx*dx+dy*dy;
}
Point median(const vector<Point>&points,Point previous){
    if(points.empty()){
        return previous;
    }
    Point current{0,0};
    for(Point point:points){
        current.x+=point.x;
        current.y+=point.y;
    }
    current.x/=points.size();
    current.y/=points.size();
    for(int iteration=0;iteration<40;iteration++){
        Point weighted{0,0},residual{0,0};
        long double weight=0;
        int coincident=0;
        for(Point point:points){
            long double distance=sqrtl(squared(point,current));
            if(distance<1e-12L){
                coincident++;
                continue;
            }
            weight+=1/distance;
            weighted.x+=point.x/distance;
            weighted.y+=point.y/distance;
            residual.x+=(point.x-current.x)/distance;
            residual.y+=(point.y-current.y)/distance;
        }
        long double norm=hypotl(residual.x,residual.y);
        if(weight==0||norm<=coincident){
            break;
        }
        // Modified Weiszfeld update is safe at coincident data points.
        long double blend=coincident/norm;
        Point next{(1-blend)*weighted.x/weight+blend*current.x,
            (1-blend)*weighted.y/weight+blend*current.y};
        long double movement=squared(next,current);
        current=next;
        if(movement<1e-18L){
            break;
        }
    }
    return current;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<Point>points(n),best;
    for(Point&point:points){
        cin>>point.x>>point.y;
    }
    long double bestScore=numeric_limits<long double>::infinity();
    for(int restart=0;restart<3;restart++){
        vector<Point>guards{points[restart*n/3]};
        while(static_cast<int>(guards.size())<k){
            long double farthest=-1;
            int selected=0;
            for(int i=0;i<n;i++){
                long double nearest=numeric_limits<long double>::infinity();
                for(Point guard:guards){
                    nearest=min(nearest,squared(points[i],guard));
                }
                if(nearest>farthest){
                    farthest=nearest;
                    selected=i;
                }
            }
            guards.push_back(points[selected]);
        }
        for(int round=0;round<=15;round++){
            vector<vector<Point>>clusters(k);
            long double score=0;
            for(Point point:points){
                int closest=0;
                for(int j=1;j<k;j++){
                    if(squared(point,guards[j])<squared(point,guards[closest])){
                        closest=j;
                    }
                }
                score+=sqrtl(squared(point,guards[closest]));
                clusters[closest].push_back(point);
            }
            if(score<bestScore){
                bestScore=score;
                best=guards;
            }
            if(round<15){
                for(int j=0;j<k;j++){
                    guards[j]=median(clusters[j],guards[j]);
                }
            }
        }
    }
    cout<<fixed<<setprecision(6);
    for(Point point:best){
        cout<<point.x<<' '<<point.y<<'\n';
    }
}