#P14724. [ICPC 2022 Seoul R] Empty Quadrilaterals
[ICPC 2022 Seoul R] Empty Quadrilaterals
Description
一个四边形是一个恰好有四个不同顶点和四条不同边的多边形,且其边之间没有任何交叉。在本问题中,给定平面上 个点的集合 ,其中任意三点不共线,要求计算所有满足以下条件的四边形的数量:其顶点是集合 中的点,并且其内部不包含 中的任何其他点。
:::align{center}
:::
例如,假设 由如上图左侧所示的五个点组成。总共有九个不同的四边形,其顶点都是 中的点,但其中只有一个四边形的内部包含 中的一个点,如上图右侧所示。因此,恰好有八个四边形满足条件,你的程序必须输出 作为正确答案。
Input Format
你的程序需要从标准输入读取数据。输入的第一行包含一个整数 (),其中 表示集合 中的点数。接下来的 行,每行包含两个整数,范围从 到 ,表示 中一个点的坐标。保证 中不存在三点共线。
Output Format
你的程序需要向标准输出写入数据。输出恰好一行,包含一个整数,表示满足条件的四边形的数量:其顶点是集合 中的点,且其内部不包含 中的任何其他点。
5
0 0
2 4
6 2
6 -2
7 3
8
4
0 0
10 0
5 10
3 2
3
10
10 10
1 0
4 8
-1 -4
-7 -4
-3 2
5 -10
-10 -5
1 1
5 -3
170
Hint
翻译由 DeepSeek V3 完成
京公网安备 11011102002149号