← 返回题目列表

AtCoder · abc418_e

H. 梯形

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

分数: 475 点

问题陈述

有 N 点在二维平面上, i坐标处的第一个点 (X_i, Y_i)。保证没有两点在同一位置,也没有三点共线。

在这四个点的组合中,有多少种组合可以形成以这四个点为顶点的梯形作为多边形?

约束

  • 4 \leq N \leq 2\,000
  • 0 \leq X_i, Y_i \leq 10^7 (1 \leq i \leq N)
  • 没有两个点位于同一位置。
  • 没有三点共线。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
\vdots
X_N Y_N

输出

将答案打印在一行上。


示例输入 1

5
0 2
0 5
1 0
2 1
2 4

示例输出 1

3

给定点的排列如下图所示。

在四个点的组合中,以下三个组合可以形成以这些点为顶点的梯形作为多边形:

  • 第 1、第 5、第 4、第 3 点。
  • 第 1、第 3、第 4、第 2 点。
  • 第1、2、5、4点。

请注意,平行四边形和矩形也被视为梯形。


示例输入 2

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

示例输出 2

22