【题解】PCB 顶点筛选问题（CEOI 2012 Day1 T2）

问题分析

题目核心

给定一个简单多边形（顶点按顺时针或逆时针顺序排列），判断每个顶点是否满足：顶点与原点的连线除顶点本身外，不与多边形其他部分相交。

关键观察

1. 简单多边形的边不交叉，仅在端点相连。
2. 顶点与原点的连线（记为射线 $L$）若满足条件，需保证：
   • 射线 $L$ 上除顶点外，无多边形的其他顶点（因顶点坐标为正整数，原点与顶点连线无其他整数点，可简化判断）；
   • 射线 $L$ 不穿过多边形的任何一条边（除顶点本身所在的两条边）。

数学工具

• 叉积：用于判断点与直线的位置关系、线段是否相交。
  • 对于点 $A(x_1,y_1)$、$B(x_2,y_2)$，叉积 $A \times B = x_1y_2 - x_2y_1$；
  • 若 $A \times B > 0$，则 $B$ 在 $A$ 的逆时针方向；若 $<0$，则在顺时针方向；若 $=0$，则两点共线。

算法设计

核心思路

1. 极角排序：将所有顶点按与原点的极角（逆时针方向）排序，便于按顺序遍历射线。
2. 边的处理：将多边形的每条边表示为“起点-终点”形式，确保起点的极角小于终点的极角（通过叉积判断，不满足则交换起点和终点）。
3. 优先队列（平衡树）：维护当前射线穿过的多边形边。遍历排序后的顶点时，通过加入/删除顶点所在的边，判断当前射线是否与其他边相交。

步骤详解

1. 输入处理与初始化：

   • 读取顶点坐标，记录顶点编号；
   • 构建多边形的边（每条边连接顶点 $i$ 和 $i+1$，顶点 $n$ 连接顶点 $1$）。

2. 边的标准化：

   • 对每条边，若起点的极角大于终点的极角，则交换起点和终点，确保边的“方向”与极角递增一致。

3. 顶点极角排序：

   • 按顶点与原点的极角逆时针排序（用叉积实现：若 $A \times B > 0$，则 $A$ 排在 $B$ 前面；共线时按 $x$ 坐标排序）。

4. 遍历与判断：

   • 用平衡树维护当前活跃的边（即与当前射线相交的边）；
   • 遍历排序后的顶点：
     • 若平衡树为空或当前射线不与平衡树中最“靠近”原点的边相交，则该顶点满足条件；
     • 加入/删除当前顶点所在的两条边（根据边的标准化方向，判断是加入还是删除边）。

5. 结果输出：

   • 收集满足条件的顶点编号，排序后输出。

数据结构选择

• 平衡树（用左偏树实现）：维护活跃边，支持高效插入、删除和查询最大值（最靠近原点的边），时间复杂度 $O(\log n)$ 每操作。
• 整体时间复杂度：$O(n \log n)$（排序 $O(n \log n)$ + 每个顶点/边的平衡树操作 $O(\log n)$），适合 $n \leq 2 \times 10^5$ 的数据规模。

代码实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 200005;
ll n, ans[N], cnt;

// 快速读入
inline char nc() {
    static char buf[1000000], *p = buf, *q = buf;
    return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q) ? EOF : *p++;
}
inline ll read() {
    ll res = 0;
    char c = nc();
    while (c < '0' || c > '9') c = nc();
    while (c <= '9' && c >= '0') res = res * 10 + c - '0', c = nc();
    return res;
}

// 快速输出
char obuf[1 << 21], *p3 = obuf;
inline void pc(char c) {
    if (p3 - obuf >= (1 << 21)) {
        fwrite(obuf, p3 - obuf, 1, stdout);
        p3 = obuf;
    }
    *p3++ = c;
}
inline void write(ll x) {
    if (x < 0) pc('-'), x = -x;
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}

// 顶点结构体（x,y坐标 + 原始编号）
struct node {
    ll x, y, num;
    // 向量减法
    node operator - (const node &b) const {
        return {x - b.x, y - b.y, 0};
    }
    // 叉积
    ll operator * (const node &b) const {
        return x * b.y - y * b.x;
    }
    // 相等判断
    bool operator == (const node &b) const {
        return x == b.x && y == b.y;
    }
} p[N];

// 边结构体（起点p0，终点p1，已标准化为p0极角 <= p1极角）
struct node2 {
    node p0, p1;
    // 边的比较函数（用于平衡树排序，判断边的优先级）
    bool operator > (const node2 &b) const {
        if (p0 == b.p0) {
            return (p1 - p0) * (b.p1 - p0) > 0;
        }
        ll op = p0 * b.p0;
        if (op > 0) {
            return (p0 - b.p0) * (p1 - b.p0) > 0;
        } else {
            return (b.p0 - p0) * (b.p1 - p0) < 0;
        }
    }
} l[N];

// 左偏树实现的平衡树（维护活跃边）
struct node3 {
    ll root = 0;
    ll lc[N], ls[N], rs[N], fa[N]; // lc：节点高度，ls/rs：左右子树，fa：父节点

    // 合并两个子树
    ll merge(ll x, ll y) {
        if (!x || !y) return x | y;
        if (l[x] > l[y]) swap(x, y); // 保持左偏树性质（小根堆，这里用>判断，实际是大根堆）
        rs[x] = merge(rs[x], y);
        fa[rs[x]] = x;
        // 维护左偏性质：左子树高度 >= 右子树高度
        if (lc[ls[x]] < lc[rs[x]]) swap(ls[x], rs[x]);
        lc[x] = lc[rs[x]] + 1;
        return x;
    }

    // 插入节点
    void push(ll x) {
        fa[x] = x;
        root = merge(root, x);
    }

    // 删除节点
    void del(ll x) {
        fa[ls[x]] = ls[x];
        fa[rs[x]] = rs[x];
        ll y = merge(ls[x], rs[x]);
        if (x == root) {
            root = y;
        } else if (x == ls[fa[x]]) {
            ls[fa[x]] = y;
            fa[y] = fa[x];
        } else {
            rs[fa[x]] = y;
            fa[y] = fa[x];
        }
    }

    // 判断是否为空
    bool empty() {
        return !root;
    }

    // 获取堆顶元素（优先级最高的边）
    node2 top() {
        return l[root];
    }
} q;

// 判断点x是否在边l的两个端点之间（极角范围内）
bool check(node2 l, node x) {
    if (l.p0 * l.p1 == 0) {
        return x.x > l.p0.x;
    } else {
        // 叉积判断x在l.p0和l.p1的极角之间，且在边的线段上（除端点）
        return l.p0 * x >= 0 && x * l.p1 >= 0 && (l.p0 - x) * (l.p1 - x) < 0;
    }
}

// 顶点按极角排序的比较函数
bool cmp(node x, node y) {
    ll c = x * y;
    if (c == 0) {
        return x.x < y.x; // 共线时，x小的在前（靠近原点）
    } else {
        return c > 0; // 逆时针方向排序
    }
}

int main() {
    n = read();
    for (ll i = 1; i <= n; i++) {
        p[i].x = read();
        p[i].y = read();
        p[i].num = i;
        l[i].p0 = p[i]; // 边i的起点是p[i]
        l[i - 1].p1 = p[i]; // 边i-1的终点是p[i]（边0对应边n）
    }
    l[n].p1 = p[1]; // 边n的终点是p[1]（闭合多边形）

    // 标准化边：确保边的起点极角 <= 终点极角
    for (ll i = 1; i <= n; i++) {
        if (!cmp(l[i].p0, l[i].p1)) {
            swap(l[i].p0, l[i].p1);
        }
    }

    // 顶点按极角排序
    sort(p + 1, p + 1 + n, cmp);

    // 遍历排序后的顶点，判断是否满足条件
    for (ll i = 1; i <= n; i++) {
        // 若活跃边为空，或当前射线不与最优先的边相交，则满足条件
        if (q.empty() || !check(q.top(), p[i])) {
            ans[++cnt] = p[i].num;
        }

        // 处理当前顶点所在的两条边（边num和边num-1，注意循环）
        ll j = p[i].num;
        // 边j：若当前顶点是边j的起点，则插入边j；否则删除边j
        if (l[j].p0 == p[i]) {
            q.push(j);
        } else {
            q.del(j);
        }

        // 边j_prev：j的前一条边（j=1时，前一条边是n）
        ll j_prev = (j + n - 2) % n + 1;
        if (l[j_prev].p0 == p[i]) {
            q.push(j_prev);
        } else {
            q.del(j_prev);
        }
    }

    // 输出结果
    write(cnt);
    pc('\n');
    sort(ans + 1, ans + 1 + cnt); // 按编号升序排列
    for (ll i = 1; i <= cnt; i++) {
        write(ans[i]);
        pc(' ');
    }

    // 刷新输出缓冲区
    fwrite(obuf, p3 - obuf, 1, stdout);
    return 0;
}

代码解释

快速读写

• 采用 fread 和 fwrite 实现快速读写，避免因输入输出量大导致超时（适配 $n \leq 2 \times 10^5$ 的数据规模）。

结构体设计

• node：存储顶点坐标和原始编号，重载减法（向量）和叉积运算符，用于极角判断和位置关系计算。
• node2：存储多边形的边，标准化为起点极角小于等于终点极角，重载比较运算符用于平衡树排序。
• node3：左偏树实现的平衡树，支持插入、删除和查询堆顶，维护当前活跃的边。

核心函数

• cmp：顶点极角排序的比较函数，用叉积判断极角方向，共线时按 $x$ 坐标排序。
• check：判断顶点是否在边的极角范围内，且边与射线相交（除顶点外）。
• 主逻辑：按极角遍历顶点，维护活跃边集合，判断当前射线是否与其他边相交，收集满足条件的顶点编号。

复杂度分析

• 时间复杂度：$O(n \log n)$，其中排序占 $O(n \log n)$，每个顶点和边的平衡树操作占 $O(\log n)$，整体满足数据规模要求。
• 空间复杂度：$O(n)$，用于存储顶点、边、结果数组和平衡树节点信息。

该算法通过极角排序和平衡树维护活跃边，高效判断每条射线是否与多边形边相交，是解决该问题的最优方案之一。