解题思路

相关算法与实现要点

• K-Means

  • 初始中心：取前 $k$ 个点作为初始中心（简单且可重复）。

  • 迭代过程：

    • 分配：每个点归到欧氏距离最近的中心；
    • 更新：每个簇的新中心为簇内点坐标的均值；

  • 终止条件：迭代次数上限 100 次，或所有中心移动距离之和 $\le 1e{-6}$。

  若出现空簇，保持其中心不变（在本题给定范围下可稳定收敛；也可按需要将最远点“拉”成新簇中心，本文实现采用保持不变的简洁策略）。

• 轮廓系数（Silhouette） 对于样本 $p$：

  • $a(p)$：与同簇其它点的平均距离；若该簇仅单个样本，则 $a(p)=0$；
  • $b(p)$：与最近的其它簇内全部点的平均距离；
  • 轮廓值：$s(p)=\dfrac{b(p)-a(p)}{\max\{a(p),\,b(p)\}} \in [-1,1]$。 簇的轮廓系数为簇内样本的 $s(p)$ 平均值。 实现时按定义直接枚举计算，时间复杂度 $O(n^2)$，对 $n\le 500$ 可接受。

• 输出与舍入

  • 输出为被选中簇中心的 $(x,y)$，采用银行家舍入保留两位：

    • Python：Decimal(...).quantize(Decimal('0.00'), ROUND_HALF_EVEN)
    • Java：BigDecimal.setScale(2, RoundingMode.HALF_EVEN)
    • C++：自写“半舍六入五留双”的函数，避免默认“四舍五入”。

代码实现

Python

import sys
from decimal import Decimal, ROUND_HALF_EVEN

def kmeans(pts, k):
    n = len(pts)
    centers = [list(pts[i]) for i in range(k)]           # 前 k 个点做初始中心
    labels = [0] * n
    for _ in range(100):                                  # 最多 100 轮
        # 分配：找最近中心
        for i in range(n):
            bi, bd = 0, (pts[i][0]-centers[0][0])**2 + (pts[i][1]-centers[0][1])**2
            for c in range(1, k):
                d = (pts[i][0]-centers[c][0])**2 + (pts[i][1]-centers[c][1])**2
                if d < bd:
                    bd, bi = d, c
            labels[i] = bi
        # 更新：按均值重算中心
        sx = [0.0]*k; sy = [0.0]*k; cnt = [0]*k
        for i in range(n):
            c = labels[i]; sx[c] += pts[i][0]; sy[c] += pts[i][1]; cnt[c] += 1
        moved = 0.0
        for c in range(k):
            nx = centers[c][0]; ny = centers[c][1]
            if cnt[c] > 0:
                nx, ny = sx[c]/cnt[c], sy[c]/cnt[c]
            moved += abs(nx - centers[c][0]) + abs(ny - centers[c][1])
            centers[c][0], centers[c][1] = nx, ny
        if moved <= 1e-6:                                 # 中心几乎不动则停止
            break
    return labels, centers

def silhouette(pts, labels, k):
    n = len(pts)
    groups = [[] for _ in range(k)]
    for i, c in enumerate(labels): groups[c].append(i)

    def dist(i, j):
        dx = pts[i][0]-pts[j][0]; dy = pts[i][1]-pts[j][1]
        return (dx*dx+dy*dy) ** 0.5

    avg = [0.0]*k
    for c in range(k):
        idx = groups[c]
        if not idx: 
            avg[c] = 0.0
            continue
        ssum = 0.0
        for i in idx:
            # a(p)
            if len(idx) == 1: a = 0.0
            else:
                t = 0.0
                for j in idx:
                    if j != i: t += dist(i, j)
                a = t / (len(idx)-1)
            # b(p)
            b = float('inf')
            for c2 in range(k):
                if c2 == c or not groups[c2]: 
                    continue
                t = 0.0
                for j in groups[c2]: t += dist(i, j)
                b = min(b, t/len(groups[c2]))
            if b == float('inf'): sp = 0.0
            else:
                m = max(a, b)
                sp = 0.0 if m == 0 else (b - a) / m
            ssum += sp
        avg[c] = ssum / len(idx)
    return avg

def rnd2(v):
    return f"{Decimal(str(v)).quantize(Decimal('0.00'), rounding=ROUND_HALF_EVEN):.2f}"

def main():
    data = list(map(float, sys.stdin.read().strip().split()))
    if not data: return
    n = int(data[0]); k = int(data[1])
    pts = [(data[i], data[i+1]) for i in range(2, 2+2*n, 2)]
    labels, centers = kmeans(pts, k)
    sil = silhouette(pts, labels, k)
    bad = min(range(k), key=lambda c: (sil[c], c))        # 轮廓系数最低
    x, y = centers[bad]
    print(f"{rnd2(x)},{rnd2(y)}")

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.math.*;

public class Main {

    static class Res {
        int[] lab; double[][] cen;
        Res(int[] l, double[][] c){ lab=l; cen=c; }
    }

    static Res kmeans(double[][] pts, int k){
        int n = pts.length;
        double[][] cen = new double[k][2];
        for(int c=0;c<k;c++){ cen[c][0]=pts[c][0]; cen[c][1]=pts[c][1]; }
        int[] lab = new int[n];

        for(int it=0; it<100; it++){
            // 分配
            for(int i=0;i<n;i++){
                int bi=0; double bd=dist2(pts[i], cen[0]);
                for(int c=1;c<k;c++){
                    double d = dist2(pts[i], cen[c]);
                    if(d<bd){ bd=d; bi=c; }
                }
                lab[i]=bi;
            }
            // 更新
            double[] sx=new double[k], sy=new double[k]; int[] cnt=new int[k];
            for(int i=0;i<n;i++){ int c=lab[i]; sx[c]+=pts[i][0]; sy[c]+=pts[i][1]; cnt[c]++; }
            double moved=0;
            for(int c=0;c<k;c++){
                double nx=cen[c][0], ny=cen[c][1];
                if(cnt[c]>0){ nx=sx[c]/cnt[c]; ny=sy[c]/cnt[c]; }
                moved += Math.abs(nx-cen[c][0])+Math.abs(ny-cen[c][1]);
                cen[c][0]=nx; cen[c][1]=ny;
            }
            if(moved<=1e-6) break;
        }
        return new Res(lab, cen);
    }

    static double dist2(double[] a, double[] b){
        double dx=a[0]-b[0], dy=a[1]-b[1];
        return dx*dx+dy*dy;
    }

    static double[] silhouette(double[][] pts, int[] lab, int k){
        int n=pts.length;
        ArrayList<Integer>[] g=new ArrayList[k];
        for(int i=0;i<k;i++) g[i]=new ArrayList<>();
        for(int i=0;i<n;i++) g[lab[i]].add(i);

        double[] avg=new double[k];
        for(int c=0;c<k;c++){
            ArrayList<Integer> idx=g[c];
            if(idx.isEmpty()){ avg[c]=0; continue; }
            double sum=0;
            for(int id: idx){
                double a;
                if(idx.size()==1) a=0;
                else{
                    double t=0;
                    for(int j: idx) if(j!=id)
                        t += Math.hypot(pts[id][0]-pts[j][0], pts[id][1]-pts[j][1]);
                    a = t/(idx.size()-1);
                }
                double b=Double.POSITIVE_INFINITY;
                for(int c2=0;c2<k;c2++){
                    if(c2==c || g[c2].isEmpty()) continue;
                    double t=0;
                    for(int j: g[c2])
                        t += Math.hypot(pts[id][0]-pts[j][0], pts[id][1]-pts[j][1]);
                    b = Math.min(b, t/g[c2].size());
                }
                double s;
                if(Double.isInfinite(b)) s=0;
                else{
                    double m=Math.max(a,b);
                    s = (m==0)?0:(b-a)/m;
                }
                sum += s;
            }
            avg[c]=sum/idx.size();
        }
        return avg;
    }

    static String r2(double v){
        BigDecimal bd=new BigDecimal(Double.toString(v)).setScale(2, RoundingMode.HALF_EVEN);
        return String.format(java.util.Locale.US, "%.2f", bd.doubleValue());
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        if(!sc.hasNext()) return;
        int n=sc.nextInt(), k=sc.nextInt();
        double[][] pts=new double[n][2];
        for(int i=0;i<n;i++){ pts[i][0]=sc.nextDouble(); pts[i][1]=sc.nextDouble(); }
        Res r=kmeans(pts,k);
        double[] sil=silhouette(pts, r.lab, k);
        int bad=0;
        for(int c=1;c<k;c++) if(sil[c]<sil[bad]) bad=c;
        System.out.println(r2(r.cen[bad][0])+","+r2(r.cen[bad][1]));
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

static inline double dist2(double x1,double y1,double x2,double y2){
    double dx=x1-x2, dy=y1-y2; return dx*dx+dy*dy;
}
static inline double dist(double x1,double y1,double x2,double y2){
    return hypot(x1-x2, y1-y2);
}

// 银行家舍入到两位
string r2(double v){
    long double s = (long double)v * 100.0L;
    long double f = floor(s);
    long double frac = s - f;
    const long double EPS = 1e-12L;
    long long u;
    if(frac > 0.5L + EPS) u = (long long)f + 1;
    else if(frac < 0.5L - EPS) u = (long long)f;
    else u = ((long long)f % 2 == 0) ? (long long)f : (long long)f + 1;
    long long ip = u / 100, fp = llabs(u % 100);
    ostringstream os; os<<ip<<'.'<<setw(2)<<setfill('0')<<fp; return os.str();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,k; if(!(cin>>n>>k)) return 0;
    vector<double> x(n), y(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];

    // K-Means：前 k 个点为初始中心
    vector<double> cx(k), cy(k);
    for(int c=0;c<k;c++){ cx[c]=x[c]; cy[c]=y[c]; }
    vector<int> lab(n);

    for(int it=0; it<100; ++it){
        // 分配
        for(int i=0;i<n;i++){
            int bi=0; double bd=dist2(x[i],y[i],cx[0],cy[0]);
            for(int c=1;c<k;c++){
                double d=dist2(x[i],y[i],cx[c],cy[c]);
                if(d<bd){ bd=d; bi=c; }
            }
            lab[i]=bi;
        }
        // 更新
        vector<double> sx(k,0), sy(k,0); vector<int> cnt(k,0);
        for(int i=0;i<n;i++){ int c=lab[i]; sx[c]+=x[i]; sy[c]+=y[i]; cnt[c]++; }
        double moved=0;
        for(int c=0;c<k;c++){
            double nx=cx[c], ny=cy[c];
            if(cnt[c]>0){ nx=sx[c]/cnt[c]; ny=sy[c]/cnt[c]; }
            moved += fabs(nx-cx[c])+fabs(ny-cy[c]);
            cx[c]=nx; cy[c]=ny;
        }
        if(moved<=1e-6) break;
    }

    // 轮廓系数
    vector<vector<int>> g(k);
    for(int i=0;i<n;i++) g[lab[i]].push_back(i);
    vector<double> sil(k,0.0);
    for(int c=0;c<k;c++){
        if(g[c].empty()) { sil[c]=0; continue; }
        double sum=0;
        for(int id: g[c]){
            double a=0;
            if(g[c].size()>1){
                for(int j: g[c]) if(j!=id) a += dist(x[id],y[id],x[j],y[j]);
                a /= (int)g[c].size()-1;
            }
            double b = numeric_limits<double>::infinity();
            for(int c2=0;c2<k;c2++){
                if(c2==c || g[c2].empty()) continue;
                double t=0;
                for(int j: g[c2]) t += dist(x[id],y[id],x[j],y[j]);
                b = min(b, t/(int)g[c2].size());
            }
            double s = isinf(b)?0:((max(a,b)==0)?0:(b-a)/max(a,b));
            sum += s;
        }
        sil[c] = sum / (int)g[c].size();
    }

    int bad=0;
    for(int c=1;c<k;c++) if(sil[c]<sil[bad]) bad=c;
    cout<<r2(cx[bad])<<","<<r2(cy[bad])<<"\n";
    return 0;
}

题目内容

【问题背景】在无线网络优化中，基站的位置分布直接影响信号覆盖质量。密集区域的基站可能造成资源浪费，而稀疏区域则会出现信号覆盖不足。

【任务要求】给定$n$个基站的二维坐标，使用K-Means算法将其划分为$k$个簇，再通过计算每个簇的轮廓系数（Silhouette Coefficient），识别信号覆盖最差的簇（轮廓系数最低），并在该簇中心新增基站以优化信号覆盖。

【算法过程】

1. 使用前$k$个基站作为初始聚类中心，执行K-Means算法。K-means的结束条件为：最大迭代次数100或者所有簇中心点移动距离都不大于$1e-6$。
2. 计算每个簇的轮廓系数（簇内所有点的轮廓系数平均值）。
3. 找出轮廓系数最低的簇。
4. 输出该簇的中心坐标（保留两位小数），作为新增基站的位置。

K-Means和轮廓系数的详细介绍见“提示”。

输入描述

第一行：基站数量 $n$ 和聚类簇数 $k$，之间以空格分开，其中 $n$ 取值范围为 $[1,500]$，$k$ 取值范围为 $[1,120]$。

接下来 $n$ 行：每行两个整数，表示基站的坐标 $x$ 和 $y$，其中 $x$ 取值范围为 $[0,5000]$，$y$ 取值范围为 $[0,3000]$。

输出描述

新增基站的坐标：$x,y$ （输出结果四舍五入保留两位小数，采用 RoundingMode.HALF_EVEN）

样例1

输入

6 2
0 0
1 1
2 2
10 10
11 11
5 5

输出

8.67,8.67

说明

簇划分结果：簇 $0:[(0,0),(1,1),(2,2)]$，中心 $(1,1);$ 簇 $1:[(5,5),(10,10)(11,11)]$，中心 $(8.67,8.67)$ 轮廓系数:簇 $0$ 的轮廓系数: $0.82$ ;簇 $1$ 轮廓系数: $0.35$ 答案:输簇 $1$ 的中心点: $(8.67,8.67)$

样例2

输入

4 2
0 0
0 1
1 0
10 10

输出

0.33,0.33

说明

簇划分结果：簇 $0$ : $[(0,0),(0,1)(1,0)]$ ，中心点: $(0.33,0.33)$ ; 簇 $[(10.10)]$ ，中心点: $(10,10)$

轮廓系数:线 $0$ 的轮廓系数: $0.92$ ;簇 $1$ 的轮廓系数: $1.0$ 答案:输出簇 $0$ 的中心点: $0.33,0.33$

簇 $0:[A(0,0),B(0,1),C(1, 0)]$ ;

簇 $1$ : $[(10. 10)]$

簇 $0$ 的轮廓系数计算:

计算点 $A(0,0)$ :

1、$A$ 同簇平均距离为 $1$ : $A$ 到 $B(0,1)$ 距离 $1$ ，$A$ 到 $C(1,0)$ 距离 $1$

2、$A$ 到簇 $1$ 平均距离为 $14.142$ : $A$ 到 $D(10,10)$ 距离 $14.142$

3、$A$ 的轮廓系数 $s(A):0.929$

计算点 $B(0,1)$ :

1、$B$ 同簇平均距离为 $1.207:B$ 到 $A (0,0)$ 距离 $1$ ，$B$ 到 $C(1,0)$ 距离 $1.414$

2、$B$ 到簇 $1$ 平均距离为 $13.454:B$ 到 $D(10,10)$ 距离 $13.454$

3、$B$ 的轮廓系数 $s(B):0.910$

计算点 $C(1,0):$ 1、$C$ 同簇平均距离为 $1.207:C$ 到 $A(0,0)$ 距离 $1，C$ 到 $B(0,1)$ 距离 $1.414$

2、$C$ 到簇 $1$ 平均距离为 $13.454:C$ 到 $D(10,10)$ 距离 $13.454$

3、$C$ 的轮廓数 $s(C):0.910$

簇 $0$ 轮廓系数: $(s(A)+s(b)+s(b))/3=2.749/3=0.92$

提示

K-means的算法步骤为：

1. 选择初始化的前 $k$ 个样本作为初始聚类中心。

2. 针对数据集中每个样本 $x_i$，计算它到 $k$ 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中。

3. 针对每个类别 $a_j$，重新计算它的聚类中心

   $$a_j = \frac{1}{c_i} \sum_{x \in c_i} x$$

   （即属于该类的所有样本的质心）。

4. 重复上面2、3两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

轮廓系数 (Silhouette Coefficient Index)：

1、对于一个数据点 $i$，先计算它和簇内其他数据点的平均距离 $a_i$。

2、然后计算该点与不包含该点所在簇的其他簇内数据点的平均距离 $b_i$（簇间相似度），选取其中距离最小的那个作为 $i$ 的簇间平均距离。

3、最后，计算数据点 $i$ 的轮廓系数：

$s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$

将所有数据点的轮廓系数取平均值，即得到聚类算法的整体轮廓系数。

若某个数据点所在簇的数据点数量小于等于1，则该点的轮廓系数为 $0$。

RoundingMode.HALF_EVEN：

1、Python默认的HALF_EVEN模式，其他语言按照如下规则处理： HALF_EVEN也称为“银行家舍入”或“向偶数舍入”。这种模式下，当小数部分恰好为$0.5$时，round()会将结果舍入到最近的偶数。

• round(2.55, 1) 会返回 $2.6$ （因为6是偶数）
• round(2.65, 1) 会返回 $2.6$ （因为6是偶数）
• round(2.75, 1) 会返回 $2.8$ （因为8是偶数）
• round(1.15, 1) 会返回 $1.2$ （因为2是偶数）