题目分析

我们需要统计满足以下条件的三角形对数量：

1. 每个三角形包含三种不同颜色的星星（红、蓝、黄各一个）
2. 两个三角形不相交（包括边界和内部）

关键思路

核心观察

两个三角形不相交的充分必要条件是：存在一条直线将两个三角形完全分离。

解法框架

1. 枚举分离直线：考虑所有通过两个给定点的直线，这样的直线有 $O(N^2)$ 条
2. 极角排序：对于每个点作为原点，将其他点按极角排序
3. 双指针统计：对于每条候选分离直线，使用双指针技术统计两侧符合条件的三角形

具体步骤

步骤1：预处理颜色组合

• 每个三角形需要包含0（红）、1（蓝）、2（黄）三种颜色各一个
• 预处理每个点对 $(A,B)$ 的颜色信息，便于快速判断三角形颜色组合

步骤2：枚举分离线

对于每个点 $O$：

• 将其他点按相对于 $O$ 的极角排序
• 按极角顺序枚举第二个点 $P$，直线 $OP$ 作为候选分离线

步骤3：统计两侧三角形

对于直线 $OP$：

• 将平面分为两个半平面
• 统计每个半平面中符合颜色要求的三角形数量
• 两个半平面的三角形数量相乘，得到以 $OP$ 为分离线的三角形对数量

步骤4：避免重复计数

• 每条分离线会被两个端点分别枚举到，因此最终结果需要除以2
• 需要确保分离线不穿过任何三角形

算法复杂度

• 枚举原点：$O(N)$
• 极角排序：$O(N \log N)$
• 双指针扫描：$O(N)$
• 总复杂度：$O(N^2 \log N)$，对于 $N \le 3000$ 可接受

实现细节

1. 使用叉积判断点的相对位置
2. 注意处理共线情况的边界条件
3. 使用模运算处理极角排序的循环特性

这种方法通过几何变换将复杂的相交判断转化为简单的半平面统计问题，是解决此类几何计数问题的典型思路。