#P3102. Sgu512 Friendly Points

    ID: 2224 传统题 1000ms 128MiB 尝试: 40 已通过: 19 难度: 8 上传者: 标签>CF2500提高+/省选-扫描线离散化树状数组单调栈消除被支配候选二分查找自定义排序规则

Sgu512 Friendly Points

题目描述

Consider nn distinct points on a plane.Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes thatcontains those two points and doesn't contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.

How many pairs of friends are there among the given points?

求这样的点对个数:以两点连线为对角线的矩形内不存在其他点(也不能在边界上)。

输入格式

The first line of the input file contains an integer nn .
The next n lines contain two integers each, the coordinates of the given points. The coordinates don't exceed 10910^9 by absolute value.

输出格式

Output one integer number — the sought number of pairs of friends.

5
0 0
0 2
2 0
2 2
1 1
8

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051 \le n \le 10^5 。