← 返回题目列表

Codeforces · 1284/E

E. 新年和城堡建设

中文机器翻译题面 查看原题

Kiwon最喜欢的视频游戏现在正在举办新年活动来激励用户!游戏的主题是建造和保卫一座城堡,这让 Kiwon 思考了以下谜题。

在二维平面中,您有一组 $$$s = \{(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\}$$$ 由 $$$n$$$ 不同点组成。在 $$$s$$$ 集合中,没有三个不同的点位于一条线上。对于一个点$$$p \in s$$$,我们可以通过建造一座城堡来保护这个点。城堡是一个简单的四边形(具有 $$$4$$$ 顶点的多边形),严格包围点 $$$p$$$ (即点 $$$p$$$ 严格位于四边形内部)。

Kiwon 对 $$$s$$$ 的 $$$4$$$ 点子集的数量感兴趣,这些子集可用于建造一座保护 $$$p$$$ 的城堡。请注意,如果单个子集可以通过多种方式连接来包围一个点,则仅计算一次。

令 $$$f(p)$$$ 为可包含点 $$$p$$$ 的 $$$4$$$ 点子集的数量。请计算 s$$$ 中所有点 $$$p 的 $$$f(p)$$$ 之和。

输入

第一行包含一个整数 $$$n$$$ ($$$5 \le n \le 2\,500$$$)。

在接下来的 $$$n$$$ 行中,给出了表示点位置的两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$)。

保证所有点都不同,并且不存在三个共线的点。

输出

打印 s$$$ 中所有点 $$$p 的 $$$f(p)$$$ 之和。

示例

输入 #1

5
-1 0
1 0
-10 -1
10 -1
0 3

输出 #1

2

输入 #2

8
0 1
1 2
2 2
1 3
0 -1
-1 -2
-2 -2
-1 -3

输出 #2

40

输入 #3

10
588634631 265299215
-257682751 342279997
527377039 82412729
145077145 702473706
276067232 912883502
822614418 -514698233
280281434 -41461635
65985059 -827653144
188538640 592896147
-857422304 -529223472

输出 #3

213