二、阅读程序（判断题请选择“正确”或“错误”，共 18 题、40 分）

阅读程序（3）

输入满足：$1\le k\le n\le100$；$1\le a[i]\le n$ 且所有 a[i] 互不相同；各点坐标为 $[0,100]$ 内的整数，所有坐标互不相同（程序使用 double 存储）。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
double x[105], y[105], cx[105], cy[105];
int n, k, a[105], id[105];
vector<int> v[105];
double dis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool solve(){
    bool flag = 0;
    for (int i = 1; i <= k; i++) v[i].clear();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            if (dis(x[i], y[i], cx[id[i]], cy[id[i]]) > dis(x[i], y[i], cx[j], cy[j]) + eps)
                id[i] = j;
        }
        v[id[i]].push_back(i);
    }
    for (int i = 1; i <= k; i++){
        double tx = cx[i], ty = cy[i];
        cx[i] = cy[i] = 0;
        for (int j = 0; j < v[i].size(); j++){
            cx[i] += x[v[i][j]];
            cy[i] += y[v[i][j]];
        }
        cx[i] /= v[i].size(); cy[i] /= v[i].size();
        if (abs(tx - cx[i]) > eps || abs(ty - cy[i]) > eps) flag = 1;
    }
    return flag;
}
double cal(){
    double ans = 0;
    for (int i = 1; i <= n; i++){
        ans += dis(x[i], y[i], cx[id[i]], cy[id[i]]);
    }
    return ans;
}
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        id[i] = 1; // 第43行
    }
    for (int i = 1; i <= k; i++){
        cin >> a[i];
        cx[i] = x[a[i]]; cy[i] = y[a[i]];
    }
    while (solve());
    printf("%.2lf", cal());
    return 0;
}

函数 solve() 的最坏时间复杂度最接近（ ）。

{{ select(1) }}

• $O(nk)$
• $O(n^2)$
• $O(k^2)$
• $O(nk\log k)$