QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100

# 8669. 正方形计数

统计

给定一个格点凸 $n$ 边形。假定 $S$ 代表改格点凸 $n$ 边形内部与边上的格点集合。询问有多少种从 $S$ 中选择四个互不相同无顺序点 $(x,y,z,w) $ 的方案,使得 $x,y,z,w$ 构成一个正方形。

Input

第一行一个整数,表示 $n$。

接下来 $n$ 行,每行两个非负整数 $(x_i,y_i)$,按照顺时针顺序表示输入的格点凸 $n$ 边形的顶点。

Output

一行一个数字,表示选择四个互不相同无顺序点 $(x,y,z,w)$ ,使得 $x,y,z,w$ 构成一个正方形的方案数。

Examples

Input 1

5
0 0
0 2
1 2
2 1
2 0

Output 1

4

Input 2

3
0 0
0 100
100 0

Output 2

1473186

Input 3

4
0 100
100 200
200 100
100 0

Output 3

34001650

Scoring

Subtask1 ($10\%$): 输入是长方形,且第一个点为左下角的点。(也就是 x,y 坐标最小的点)

Subtask2 ($25\%$): 输入是直角三角形,左下角为直角,且第一个点为左下角的点。(也就是 x,y 坐标最小的点)

Subtask3 ($15\%$):$n \le 8, 0\le x_i, y_i \le 10$

Subtask4 ($20\%$):$n \le 8, 0\le x_i, y_i \le 300$

Subtask5 ($15\%$):$n \le 8, 0\le x_i, y_i \le 800$

Subtask6 ($15\%$):$n \le 8, 0\le x_i, y_i \le 2000$