面试题：C++ STL算法sort复杂自定义排序规则

Question

给定一个二维向量 `std::vector<std::vector<int>> matrix`，每个子向量代表一个点的坐标 `{x, y}`。请使用 `std::sort` 对 `matrix` 进行排序，排序规则为：先按点到原点 `(0, 0)` 的距离从小到大排序，如果距离相同，则按 `x` 坐标从小到大排序，如果 `x` 坐标也相同，则按 `y` 坐标从小到大排序。请写出完整的排序函数实现。

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

// 计算点到原点的距离
double distance(const std::vector<int>& point) {
    return std::sqrt(point[0] * point[0] + point[1] * point[1]);
}

// 比较函数
bool comparePoints(const std::vector<int>& a, const std::vector<int>& b) {
    double distA = distance(a);
    double distB = distance(b);
    if (distA != distB) {
        return distA < distB;
    } else if (a[0] != b[0]) {
        return a[0] < b[0];
    } else {
        return a[1] < b[1];
    }
}

// 排序函数
void sortPoints(std::vector<std::vector<int>>& matrix) {
    std::sort(matrix.begin(), matrix.end(), comparePoints);
}

你可以通过以下方式调用这个函数：

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 3},
        {2, 2},
        {4, 1}
    };
    sortPoints(matrix);
    for (const auto& point : matrix) {
        std::cout << "{" << point[0] << ", " << point[1] << "}" << std::endl;
    }
    return 0;
}