C语言，密切接触者追踪

Question

假如每个人身上都携带着正常运行的手机，而且电信运营商能采集和存储每台手机每隔一定时间的准确位置信息(位置信息存储为“9位整数的时间戳 手机用户编号 经度纬度”，比如:
134356782 100 25658827 25657689)，那么在发生新冠肺炎疫情的时候，从技术层面就能做到对密接者的准确追踪。假设某个小镇有1万人，所有人的位置信息被电信运营商按小时分类集中存在某个文件里。为了方便大家计算，我们假设经度为8位数的整数、纬度也为8位数的整数，假设时间戳相差在2之内、且经度相差为3之内而且纬度也相差为3之内就视为密接者。
A、假如老张的用户编号为5，他被确诊新冠肺炎，防控办需根据电信运营商的记录文件追踪老张的密接者，以及密接者的密接者、密接者的密接者的密接者.……最后把所有密接者的位置信息“时间戳、用户手机编号、经度、纬度”输出来。
B、思考:如果是千万人口级别的大都市怎么办?

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下。
A问题代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义每个位置信息的结构体
struct Position {
    int timestamp;
    int user_id;
    int longitude;
    int latitude;
};

// 判断两个位置信息是否是密接者
int is_close_contact(struct Position p1, struct Position p2) {
    if (abs(p1.timestamp - p2.timestamp) <= 2 &&
        abs(p1.longitude - p2.longitude) <= 3 &&
        abs(p1.latitude - p2.latitude) <= 3) {
        return 1;
    }
    return 0;
}

int main() {
    int user_id = 5;  // 老张的用户编号
    int num_positions = 10000;  // 总共的位置信息数量
    struct Position* positions = (struct Position*)malloc(sizeof(struct Position) * num_positions);

    // 从文件中读取位置信息
    FILE* fp = fopen("position.txt", "r");
    if (fp == NULL) {
        printf("Cannot open file!\n");
        return 0;
    }
    for (int i = 0; i < num_positions; i++) {
        fscanf(fp, "%d %d %d %d", &positions[i].timestamp, &positions[i].user_id, &positions[i].longitude, &positions[i].latitude);
    }
    fclose(fp);

    // 查找密接者
    int close_contacts[10000];
    int num_close_contacts = 0;
    for (int i = 0; i < num_positions; i++) {
        if (positions[i].user_id == user_id) {
            for (int j = 0; j < num_positions; j++) {
                if (i != j && is_close_contact(positions[i], positions[j])) {
                    int is_new = 1;
                    for (int k = 0; k < num_close_contacts; k++) {
                        if (positions[j].user_id == close_contacts[k]) {
                            is_new = 0;
                            break;
                        }
                    }
                    if (is_new) {
                        close_contacts[num_close_contacts++] = positions[j].user_id;
                    }
                }
            }
        }
    }

    // 输出密接者的位置信息
    for (int i = 0; i < num_positions; i++) {
        for (int j = 0; j < num_close_contacts; j++) {
            if (positions[i].user_id == close_contacts[j]) {
                printf("%d %d %d %d\n", positions[i].timestamp, positions[i].user_id, positions[i].longitude, positions[i].latitude);
            }
        }
    }

    free(positions);
    return 0;
}

B问题的思考如下：

针对千万人口级别的大都市，为了保证算法的效率和精度，可以采用以下措施：

1、分区域存储位置信息，每个区域的范围不超过1000平方公里，每个区域内部使用二叉搜索树或哈希表等数据结构存储位置信息，方便快速查找密接者。
2、优化密接者查找算法，使用图论中的最短路径算法或社交网络分析算法等，避免遍历所有位置信息的情况出现

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢