题目大意

给定平面上 $n$ 个点，保证任意三点不共线。将所有点两两连线，问有多少条线段不与其他任何线段在非端点处相交。

解题思路

关键观察

对于一条线段 $AB$，它不与其他线段相交的充要条件是：线段 $AB$ 两侧的点数乘积等于线段 $AB$ 两侧形成的三角形数量之和。

更具体地说：

• 设线段 $AB$ 将平面分成左右两部分
• 左侧有 $L$ 个点，右侧有 $R$ 个点
• 那么以 $AB$ 为公共边的三角形数量为：左侧点与右侧点连成的跨越 $AB$ 的三角形数量

算法核心

对于每个点 $i$，我们：

1. 以 $i$ 为原点，计算其他所有点相对于 $i$ 的极角
2. 按极角排序后，使用双指针扫描，对于每个方向 $j$，找到与其夹角小于 $180^\circ$ 的所有点
3. 统计各种组合数，最终判断每条线段是否满足条件

判断条件

对于线段 $AB$：

• all[A][B] 表示线段 $AB$ 两侧点数的乘积
• ao[A][B] + ao[B][A] 表示跨越线段 $AB$ 的三角形数量

当且仅当两者相等时，线段 $AB$ 不与任何其他线段相交。

复杂度分析

• 对于每个点：$O(n)$ 时间计算极角
• 排序：$O(n \log n)$
• 双指针扫描：$O(n)$
• 总复杂度：$O(n^2 \log n)$，对于 $n \le 1000$ 可以接受

总结

本题的关键在于将几何问题转化为组合计数问题，通过极角排序和双指针技巧高效统计各种组合数，最终利用充要条件判断每条线段是否满足要求。