给定一个格点凸 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%):n≤8,0≤xi,yi≤10
Subtask4 (20%):n≤8,0≤xi,yi≤300
Subtask5 (15%):n≤8,0≤xi,yi≤800
Subtask6 (15%):n≤8,0≤xi,yi≤2000