QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#5079. Empty Quadrilaterals

統計

四边形是一个恰好有四个不同顶点和四条不同边,且边与边之间没有交叉的多边形。在本题中,给定平面上的一个点集 $P$,其中包含 $n$ 个点,且任意三点不共线。你需要计算满足以下条件的四边形的数量:四边形的四个顶点均属于点集 $P$,且其内部不包含 $P$ 中的任何其他点。

例如,假设 $P$ 由上图左侧所示的五个点组成。以 $P$ 中的点为顶点的不同四边形共有九个,而其中只有一个四边形的内部包含 $P$ 中的一个点,如上图右侧所示。因此,满足条件的四边形恰好有八个,你的程序必须输出 8 作为正确答案。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($1 \le n \le 300$),表示点集 $P$ 中的点数。接下来的 $n$ 行,每行包含两个整数,取值范围在 $-10^9$ 到 $10^9$ 之间,表示 $P$ 中一个点的坐标。$P$ 中不存在三点共线的情况。

输出格式

程序向标准输出写入数据。输出一行,包含一个整数,表示顶点属于点集 $P$ 且内部不包含 $P$ 中其他点的四边形的数量。

样例

样例输入 1

5
0 0
2 4
6 2
6 -2
7 3

样例输出 1

8

样例输入 2

4
0 0
10 0
5 10
3 2

样例输出 2

3

样例输入 3

10
10 10
1 0
4 8
-1 -4
-7 -4
-3 2
5 -10
-10 -5
1 1
5 -3

样例输出 3

170

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.