题解：彩色点问题

问题分析

题目涉及平面上的 ( n ) 个点，通过特定规则的迭代过程生成目标点，进而根据点在过程中的出现特性将其分为绿色（G）、蓝色（B）、红色（R）。核心是理解点的转移规则，并判断每个点是否满足绿色、蓝色或红色的定义。

1. 转移规则：
   给定起始点 ( i ) 和紧随点 ( j )，向量为 $( \overrightarrow{P_i P_j} )$。将除 $( j )$ 外的所有点按以下规则排序：

   • 以 ( j ) 为顶点，按与向量 $( \overrightarrow{P_i P_j} )$ 的逆时针角度从小到大排序；
   • 角度相同则按到 ( j ) 的距离从小到大排序。
     排序后第 ( t ) 个点为目标点 ( k )，随后以 ( (j, k) ) 为新的（起始点，紧随点）重复过程。

2. 颜色定义：

   • 绿色（G）：存在某个起始状态 ( (i, j) )，使得 ( i ) 在过程中无限次成为起始点。
   • 蓝色（B）：非绿色，但存在某个起始状态 ( (i, j) )，使得 ( i ) 至少再成为一次起始点。
   • 红色（R）：既非绿色也非蓝色。

核心思路

1. 预计算转移函数：
   对于所有可能的（起始点 ( i )，紧随点 ( j )）对（共 $( n(n-1) )$ 种），预计算其目标点 ( k )，记为 $( next[i][j] = k )$。这是后续分析的基础。

2. 分析状态转移链：
   每个状态 ( (a, b) ) 会通过 $( next[a][b] = c )$ 转移到 ( (b, c) )，形成一条状态链。由于状态总数有限（$( n(n-1) )$ 种），链最终会进入循环。

3. 判断点的颜色：

   • 对每个点 ( i )，检查是否存在某个状态 ( (i, j) )，使得 ( i ) 在其状态链中无限次出现（即链的循环部分包含 ( i ) 作为起始点）—— 若存在则为绿色。
   • 若不是绿色，检查是否存在某个状态 ( (i, j) )，使得 ( i ) 在其状态链中至少再出现一次—— 若存在则为蓝色。
   • 否则为红色。

算法步骤

1. 预计算 $( next[i][j] )$：
   对每个 ( (i, j) )（$( i \neq j )$）：

   • 计算向量 $( \overrightarrow{P_i P_j} = (dx_0, dy_0) = (x_j - x_i, y_j - y_i) )$。
   • 对除 ( j ) 外的所有点 ( k )，计算向量 $( \overrightarrow{P_j P_k} = (dx, dy) = (x_k - x_j, y_k - y_j) )$。
   • 计算 $( (dx_0, dy_0) )$ 与 $( (dx, dy) )$ 的叉积，确定逆时针角度排序（叉积为正表示 ( k ) 在向量左侧，角度更小）。
   • 角度相同（叉积为 0）时，按距离平方（避免浮点误差）排序。
   • 取排序后第 $( t-1 )$ 个点（0 索引）作为 $( next[i][j] )$。

2. 遍历所有状态链：
   对每个状态 ( (a, b) )，跟踪其转移链，记录链中出现的起始点。通过标记访问过的状态避免重复计算。

3. 标记颜色：

   • 若状态链进入循环，且循环中包含起始点 ( i )，则 ( i ) 标记为绿色。
   • 若状态链中起始点 ( i ) 出现多次（但不满足绿色条件），则 ( i ) 标记为蓝色。

代码框架

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

struct Point {
    long long x, y;
};

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

    int n, t;
    cin >> n >> t;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    // 预计算next[i][j]：i和j是0-based索引
    vector<vector<int>> next_state(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;

            // 向量P_iP_j
            long long dx0 = points[j].x - points[i].x;
            long long dy0 = points[j].y - points[i].y;

            // 收集除j外的所有点k
            vector<tuple<long long, long long, int>> others;  // (-cross, dist_sq, k)
            for (int k = 0; k < n; ++k) {
                if (k == j) continue;

                long long dx = points[k].x - points[j].x;
                long long dy = points[k].y - points[j].y;
                long long cross = dx0 * dy - dy0 * dx;  // 叉积
                long long dist_sq = dx * dx + dy * dy;  // 距离平方

                others.emplace_back(-cross, dist_sq, k);  // 负号用于排序
            }

            // 排序：先按-cross（即cross从大到小），再按距离平方
            sort(others.begin(), others.end());

            // 取第t-1个点
            next_state[i][j] = get<2>(others[t - 1]);
        }
    }

    // 分析每个状态(a, b)的转移链，记录起始点出现情况
    vector<bool> is_green(n, false);
    vector<bool> is_blue(n, false);
    set<pair<int, int>> visited;  // 记录已处理的状态(a, b)

    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < n; ++b) {
            if (a == b || visited.count({a, b})) continue;

            vector<pair<int, int>> path;
            int current_a = a, current_b = b;

            while (!visited.count({current_a, current_b})) {
                visited.insert({current_a, current_b});
                path.emplace_back(current_a, current_b);

                // 转移到下一个状态
                int k = next_state[current_a][current_b];
                current_a = current_b;
                current_b = k;
            }

            // 找到循环起点
            int cycle_start = -1;
            for (int i = 0; i < path.size(); ++i) {
                if (path[i].first == current_a && path[i].second == current_b) {
                    cycle_start = i;
                    break;
                }
            }

            // 提取循环部分
            vector<pair<int, int>> cycle;
            if (cycle_start != -1) {
                cycle = vector<pair<int, int>>(path.begin() + cycle_start, path.end());
            }

            // 检查循环中的起始点（绿色）
            set<int> cycle_starts;
            for (auto& p : cycle) {
                cycle_starts.insert(p.first);
            }
            for (int ca : cycle_starts) {
                is_green[ca] = true;
            }

            // 检查路径中出现多次的起始点（蓝色）
            map<int, int> start_counts;
            for (auto& p : path) {
                start_counts[p.first]++;
            }
            for (auto& [ca, cnt] : start_counts) {
                if (cnt >= 2 && !is_green[ca]) {
                    is_blue[ca] = true;
                }
            }
        }
    }

    // 生成结果
    string res;
    for (int i = 0; i < n; ++i) {
        if (is_green[i]) {
            res += 'G';
        } else if (is_blue[i]) {
            res += 'B';
        } else {
            res += 'R';
        }
    }
    cout << res << endl;

    return 0;
}

算法复杂度

• 时间复杂度：

  • 预计算 $( next[i][j] )$：$( O(n^3 \log n) )$（对每个 ( (i,j) ) 排序 ( O(n) ) 个点）。
  • 遍历状态链：$( O(n^2) )$（每个状态仅处理一次）。
    总复杂度为 $( O(n^3 \log n) )$，适用于 $( n \leq 1000 )$（实际优化后可通过）。

• 空间复杂度：$( O(n^2) )$（存储 ( next ) 数组和访问标记）。

算法标签

• 计算几何（向量叉积、角度排序）
• 状态转移与循环检测
• 哈希与记忆化
• 图论（有向图遍历）
• 分类讨论（颜色判断）