#L3054. 「HNOI2019」鱼

    ID: 3710 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>计算几何极角排序、双指针、组合计数

「HNOI2019」鱼

题目描述

在平面坐标系上给定 nn 个不同的整点(也即横坐标与纵坐标皆为整数的点)。我们称从这 nn 个点中选择 66 个不同的点所组成的有序六元组 A,B,C,D,E,F\langle A,B,C,D,E,F\rangle 是一条「鱼」,当且仅当满足以下条件:

  1. AB=ACAB = AC(身形要对称)
  2. BD=CDBD = CD
  3. DE=DFDE = DF
  4. BAD,BDA\angle BAD,\angle BDACAD,CDA\angle CAD,\angle CDA 都是锐角(脑袋和屁股显然不能是凹的)
  5. ADE,ADF\angle ADE,\angle ADF 大于 9090^\circ(也即为钝角或平角,为了使尾巴不至于翘那么别扭)

下图就是一个合法的鱼的例子:

其中点的组成相同,但顺序不同的鱼视为不同的鱼,即 A,B,C,D,E,F\langle A,B,C,D,E,F\rangleA,C,B,D,E,F\langle A,C,B,D,E,F\rangle 视为不同的两条鱼(毕竟鱼也有背和肚子的两面),同理 A,B,C,D,E,F\langle A,B,C,D,E,F\rangleA,B,C,D,F,E\langle A,B,C,D,F,E\rangle 也可以视为不同的两条鱼(假设鱼尾巴可以打结)。

问给定的 nn 个点可以构成多少条鱼。

特别提醒:数据保证 nn 个点互不重复。

输入格式

第一行一个正整数 nn,代表平面上点的个数。

接下来 nn 行每行两个整数 x,yx,y,代表点的横纵坐标。

输出格式

输出一行一个非负整数,代表鱼的个数。

样例

输入

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

输出

16

数据范围与提示

  • 对于前 20%20\% 的数据,保证 n10,0x,y5n \le 10, 0 \le |x|, |y| \le 5
  • 对于前 40%40\% 的数据,保证 n300,0x,y105n \le 300, 0 \le |x|, |y| \le 10^5
  • 对于另外 20%20\% 的数据,保证 x,y20|x|, |y| \le 20
  • 对于所有数据,保证 6n1000,0x,y1096 \le n \le 1000, 0 \le |x|, |y| \le 10^9nn 个点互不重复。