# Friendly Points

## 题目描述

Consider $n$ 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 that contains 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?

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
int x, y;
friend bool operator<(Point const &a, Point const &b) {
return a.x < b.x;
}
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
for (; l <= L && p[L].y == p[mid].y; --L)
;
for (; R <= r && p[R].y == p[mid].y; ++R)
;
if (l > L && R > r) {
std::sort(p + l, p + r + 1);
return void(ans += r - l);
}
mid = l <= L ? L : R - 1;
int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
calc(l, mid), calc(mid + 1, r);
for (; p1 <= mid && p2 <= r;) {
int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
mx = std::max(mx, p[p1].y);
for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
mn = std::min(mn, p[p2].y);
for (; t1 && s1[t1 - 1].y < mx; --t1)
;
for (; t2 && s2[t2 - 1].y > mn; --t2)
;
Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
for (; t1 && s1[t1 - 1].y == mx; --t1)
;
for (; t2 && s2[t2 - 1].y == mn; --t2)
;
if (mx > -MAX)
ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
if (mn < MAX)
ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
}
for (; p1 <= mid;) {
int x = p[p1].x, mx = -MAX;
for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
mx = std::max(mx, p[p1].y);
for (; t1 && s1[t1 - 1].y < mx; --t1)
;
Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
for (; t1 && s1[t1 - 1].y == mx; --t1)
;
ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
}
for (; p2 <= r;) {
int x = p[p2].x, mn = MAX;
for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
mn = std::min(mn, p[p2].y);
for (; t2 && s2[t2 - 1].y > mn; --t2)
;
Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
for (; t2 && s2[t2 - 1].y == mn; --t2)
;
ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
}
for (int i = l; i <= r; ++i)
p[i] = tmp[i];
}

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
calc(0, n - 1), printf("%I64d\n", ans);
return 0;
}


418 I'm a teapot