QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100
[-38]

# 8669. 正方形计数

Statistics

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

Input

第一行一个整数,表示 n

接下来 n 行,每行两个非负整数 (xi,yi),按照顺时针顺序表示输入的格点凸 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%):n8,0xi,yi10

Subtask4 (20%):n8,0xi,yi300

Subtask5 (15%):n8,0xi,yi800

Subtask6 (15%):n8,0xi,yi2000