#4739. 「KTSC 2019 R1」山羊 题解

题目理解

这是一个计算几何问题：给定 $N$ 个点（山羊位置），对于每个查询 $(A,B,C)$，需要计算被标记三次的山羊数量。

关键几何理解：

• 每只山羊的视野是 $180^\circ$
• 标记规则：对于每个选定的山羊，标记它看到的另外两个点亮山羊之间（按角度排序）的所有山羊
• 最终统计被三个选定山羊都标记的山羊数量

核心算法

算法标签：计算几何 凸包 极角排序 前缀和 角度区间处理

1. 算法框架

预处理阶段 (init 函数)

void init(std::vector<int> X, std::vector<int> Y) {
    // 1. 计算凸包
    ch();
    
    // 2. 为每个点预处理极角排序和前缀和
    for (int i = 0; i < N; ++i) {
        // 将其他点分为"小于"和"大于"当前点的两组
        // 按极角排序
        // 计算accsum[i][j]和eqcnt[i][j]
    }
}

查询阶段 (count 函数)

int count(int A, int B, int C) {
    // 处理边界情况（三点共线）
    // 计算角度区间交集
    // 返回被标记三次的山羊数量
}

2. 关键数据结构

凸包计算

void ch() {
    // 使用Andrew算法计算凸包
    // 分别计算上凸包和下凸包
    // 合并得到完整凸包
    // 记录每个点是否在凸包上及位置索引
}

算法标签：凸包算法 Andrew算法 单调链

极角排序预处理

对于每个点 $i$：

• 将其他点分为两组：$P[j] < P[i]$ 和 $P[j] > P[i]$
• 按极角（相对于点 $i$）排序
• 计算 accsum[i][j]：点 $j$ 在排序中的累积位置
• 计算 eqcnt[i][j]：与点 $j$ 共线的点数

算法标签：极角排序 叉积判断 共线处理

3. 查询处理逻辑

基本情况处理

// 确保B和C在凸包上
if (onhull[B] == -1) swap(A, B);
if (onhull[C] == -1) swap(A, C);

// 处理三点共线情况
if (ccwval == 0 && onhull[A] != -1) {
    // 特殊处理共线情况
}

核心计算

int tABC = accsum[A][C] - accsum[A][B] + eqcnt[A][C];
int tBC = accsum[B][C] - accsum[B][next_pt(B)];
int ans = tABC - tBC + 1;

几何意义：

• tABC：从点A看，在B到C角度区间内的点数
• tBC：从点B看的相关区间点数
• 最终结果：三个视野的角度区间交集大小

算法正确性分析

为什么这样计算交集？

1. 极角排序：每个点维护其他点的角度顺序
2. 前缀和：快速计算角度区间内的点数
3. 凸包性质：利用凸包结构简化计算
4. 区间交集：通过相对位置计算三个 $180^\circ$ 视野的交集

关键技巧

• 叉积判断：ccw 函数判断点的相对方位
• 共线处理：特殊处理三点共线情况
• 循环处理：处理角度环绕情况

复杂度分析

• 预处理：$O(N^2 \log N)$，每个点需要排序
• 单次查询：$O(1)$，使用预处理信息
• 总复杂度：$O(N^2 \log N + Q)$，满足数据范围要求

算法标签总结

主要标签

• 计算几何 - 问题领域
• 凸包 - 核心数据结构
• 极角排序 - 关键技术

技术标签

• 前缀和 - 快速区间查询
• 叉积运算 - 方位判断
• 区间交集 - 问题本质

几何算法标签

• Andrew算法 - 凸包计算方法
• 角度区间 - 视野建模
• 共线检测 - 边界情况处理

优化标签

• 预处理 - 离线计算加速查询
• $O(1)$查询 - 高效响应
• 循环处理 - 处理环形角度

关键创新点

1. 极角排序预处理：为每个点预计算其他点的角度顺序
2. 凸包利用：利用凸包性质简化计算
3. 前缀和技巧：快速计算角度区间内的点数
4. 统一处理框架：处理一般情况和边界情况

样例验证

对于样例查询 count(0, 5, 2)：

• 计算三个点的相对位置和角度区间
• 确定每个点的 $180^\circ$ 视野范围
• 计算三个视野的交集大小
• 返回结果 $4$

这个解法通过精妙的几何预处理和高效的角度区间计算，解决了复杂的多视野交集问题。