#P14721. [Bulgarian2022春季赛]pairs
[Bulgarian2022春季赛]pairs
题目描述
给定平面上 个整点。对于一对点,如果存在一个边平行于坐标轴的矩形,使得:
- 这两个点都包含在该矩形中;
- 且没有任何其他点包含在该矩形中;
那么我们称这对点是接近的。
若一个点位于矩形内部或边界上,则认为该点被矩形包含。矩形顶点的坐标可以是小数。
请你求出接近点对的数量。
输入格式
标准输入第一行包含一个整数 ,表示点的个数。
接下来 行,每行包含两个整数 ,表示对应点的坐标。
输出格式
标准输出输出一行一个整数,表示接近点对的数量。
数据范围
- 不存在两个点位于同一个位置
子任务与评分
要获得某个子任务的分数,你的程序必须通过该子任务中的所有测试。
| 子任务 | 分值 | 额外限制 | |
|---|---|---|---|
| 1 | 11 | 500 | - |
| 2 | 20 | 4000 | |
| 3 | 17 | 10000 | |
| 4 | 32 | 300000 | 不存在两点位于同一条竖直线或同一条水平线上。即对任意 ,有 且 |
| 5 | 20 | - |
样例
输入
6
-1 -1
1 1
1 0
-1 0
-2 0
2 2
输出
5
样例说明
在给出的 6 个点中,恰好有 5 对满足条件的点对。
