#P3543. [ONTAK2010]Garden

    ID: 2753 传统题 2000ms 128MiB 尝试: 571 已通过: 133 难度: 7 上传者: 标签>难度分类提高数据结构根号分治枚举与搜索组合枚举哈希表CF2200BySbullet

[ONTAK2010]Garden

[ONTAK2010] Garden

题目描述

巴伊托利娜要在家附近建一个正方形花园。花园的边必须平行于坐标轴,四个角各有一棵苹果树。

给定附近全部苹果树的位置。她检查每一种符合条件的花园位置需要一秒,请计算检查完所有可能的位置需要多少秒。四个顶点的位置确定一个花园。

输入格式

第一行一个整数 nn,表示苹果树的数量。接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 棵树的坐标。各坐标对互不相同。

输出格式

一行一个整数,表示边与坐标轴平行、四个顶点都有苹果树的正方形数量。

样例 #1

6
0 0
0 1
1 0
1 1
3 0
3 1
1

坐标 (0,0)(0,0)、(0,1)(0,1)、(1,0)(1,0)、(1,1)(1,1) 构成唯一一种花园。

数据范围

1≤n≤1000001\le n\le100000,−106≤xi,yi≤106-10^6\le x_i,y_i\le10^6。