简单解题思路

问题描述

给定三维空间中的 n 个点，每个点有一个类别标识（id）。要求找到一个距离 r，使得在以 r 为半径的范围内：

1. 不同类别的点尽可能分离（即不同类别的点对数量最大化）；
2. 同类别的点尽可能聚集（即同类别的点对数量最小化）。

最终输出满足条件的最大点对数量 num 和对应的距离 r（取平方根后的实际距离）。

核心思路

1. 计算所有点对距离：

   • 预处理所有点对之间的欧氏距离平方（避免开方运算，提高效率）。

2. 排序所有距离：

   • 将计算出的所有点对距离按从小到大排序。

3. 滑动窗口统计：

   • 从小到大遍历每个距离 dis[i]，动态维护当前距离下的点对状态：
     • 如果两点类别不同，减少它们的计数（模拟分离）；
     • 如果两点类别相同，增加它们的计数（模拟聚集）。
   • 统计当前距离下满足条件的点对数量 cnt。

4. 记录最优解：

   • 在遍历过程中，记录使 cnt 最大的距离 r 及其对应的 num。

关键步骤

1. 输入处理：

   • 读取每个点的坐标 (x, y, z) 和类别 id。

2. 距离计算与排序：

   • 计算所有点对的欧氏距离平方，并排序。

3. 动态统计：

   • 使用滑动窗口方法，动态更新每个距离下的点对状态。
   • 维护当前距离下的最优解 (num, r)。

4. 输出结果：

   • 输出最大点对数量 num 和对应的实际距离 sqrt(r)。

总结

• 核心算法：暴力枚举 + 排序 + 滑动窗口统计。
• 适用场景：空间聚类分析、距离阈值优化。
• 优化点：通过距离平方避免浮点运算，利用排序简化统计过程。

#include <cstdio>
#include <algorithm>
#include <cmath>

// 定义节点结构体
struct node
{
    int id, x, y, z;
} sta[1005];

// 定义距离结构体
struct node1
{
    int be, fin, len;
    bool operator < (const node1& a) const{
        return len < a.len;
    }
} dis[1005*1005];

int numb[1005];

// 计算两点之间距离的函数
int getdis(int a, int b);

// 计算平方的函数
int pw(int x);

int main()
{
    int n;
    while (scanf ("%d", &n) != EOF) {
        int k = 0, x, y, z, p;
        for (int i = 1; i <= n; i++) {
            scanf ("%d%d%d%d", &x, &y, &z, &p);
            sta[i] = (node){p, x, y, z};
            numb[i] = 1;
        }
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                dis[++k].be = i; dis[k].fin = j;
                dis[k].len = getdis(i, j);
            }
        int r = 0, num = 0, cnt = 0;
        // 使用 std::sort 函数，明确指定迭代器范围
        std::sort(dis + 1, dis + 1 + k);
        for (int i = 1; i <= k; i++) {
            int xx = dis[i].be, yy = dis[i].fin;
            if (sta[xx].id != sta[yy].id) {
                numb[xx]--;
                numb[yy]--;
                if (numb[xx] == -1) cnt++;
                if (numb[yy] == -1) cnt++;
            }
            else {
                numb[xx]++;
                numb[yy]++;
                if (numb[xx] == 0) cnt--;
                if (numb[yy] == 0) cnt--;
            }
            if (i != k && dis[i].len == dis[i + 1].len) continue;
            if (num < cnt) {
                num = cnt;
                r = dis[i].len;
            }
        }
        printf ("%d\n%.4f\n", num, std::sqrt(r * 1.0));
    }
    return 0;
}

// 计算平方的函数实现
int pw(int x)
{
    return x * x;
}

// 计算两点之间距离的函数实现
int getdis(int a, int b)
{
    int sum = pw(sta[a].x - sta[b].x) + pw(sta[a].y - sta[b].y) + pw(sta[a].z - sta[b].z);
    return sum;
}