AdditionalFile5662.zip

#5662. 「POI2026 R3」Zliczanie Z

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – III etap Zliczanie Z

Bajtek 最近学会了如何书写字母 $Z$。从那时起，他开始在各个角落发现它：在杂志里、在茶叶渣中，甚至在夜晚的星空里。对于 Bajtek 而言，如果一个由四个互不相同的点构成的有序四元组 $(A, B, C, D)$ 满足 $0^{\circ} < \measuredangle ABC = \measuredangle DCB < 90^{\circ}$，则它构成了一个字母 $Z$。其中 $\measuredangle ABC$ 表示由点 $A, B, C$ 构成的、按逆时针方向计算的角的度数。

根据 Bajtek 的定义，在下图中只有第 $4$ 张和第 $5$ 张图中的四点组 $(A, B, C, D)$ 构成了字母 $Z$（以绿色实线标注）。

男孩现在想知道，在他最喜欢的平面点集（包含 $n$ 个点）中共有多少个字母 $Z$。请帮他计算出这个数量！

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 1500)$，表示 Bajtek 考虑的点数。接下来的 $n$ 行描述这些点。其中第 $i$ 行包含两个整数 $x_i, y_i$ $(0 \leq x_i, y_i \leq 10^9)$，表示第 $i$ 个点的坐标。可以假设输入中给出的点两两不同。

输出格式

第一行应当输出构成字母 $Z$ 的有序四元组 $(A, B, C, D)$ 的数量。

样例

输入

4
0 0
1 0
0 2
1 2

输出

4

构成字母 $Z$ 的点编号四元组为：

• ($2, 1, 4, 3$)
• ($3, 4, 1, 2$)
• ($1, 3, 2, 4$)
• ($4, 2, 3, 1$)

附加样例

• $\texttt{0a}$：上述样例。此外：
• $\texttt{0b}$：$n=9$，点分布在左下角为 $(0,0)$、右上角为 $(2,2)$ 的正方形内；
• $\texttt{0c}$：满足子任务 $2$ 限制的测试点，其中 $k=4$；
• $\texttt{0d}$：$n=1500$，随机选取的满足 $x=y$ 或 $x=y+1$ 的点。

数据范围与提示

详细子任务附加限制及分值如下表所示。