#P14721. [Bulgarian2022春季赛]pairs

    ID: 13937 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500分治排序单调栈计算几何数据结构二分扫描线

[Bulgarian2022春季赛]pairs

题目描述

给定平面上 NN 个整点。对于一对点,如果存在一个边平行于坐标轴的矩形,使得:

  • 这两个点都包含在该矩形中;
  • 没有任何其他点包含在该矩形中;

那么我们称这对点是接近的

若一个点位于矩形内部或边界上,则认为该点被矩形包含。矩形顶点的坐标可以是小数

请你求出接近点对的数量。

输入格式

标准输入第一行包含一个整数 NN,表示点的个数。

接下来 NN 行,每行包含两个整数 xi,yix_i, y_i,表示对应点的坐标。

输出格式

标准输出输出一行一个整数,表示接近点对的数量。

数据范围

  • N300000N \le 300000
  • xi,yi109|x_i|, |y_i| \le 10^9
  • 不存在两个点位于同一个位置

子任务与评分

要获得某个子任务的分数,你的程序必须通过该子任务中的所有测试。

子任务 分值 NN \le 额外限制
1 11 500 -
2 20 4000
3 17 10000
4 32 300000 不存在两点位于同一条竖直线或同一条水平线上。即对任意 iji \ne j,有 xixjx_i \ne x_jyiyjy_i \ne y_j
5 20 -

样例

输入

6
-1 -1
1 1
1 0
-1 0
-2 0
2 2

输出

5

样例说明

在给出的 6 个点中,恰好有 5 对满足条件的点对。