题目分析

这是一个有向图最短路和问题，但图是特殊的：

• 每个点向**第一象限（右下）和第三象限（左上）**的点连边
• 边权为 1
• 需要求每个点到其他所有点的最短距离和

直接 BFS 是 (O(N^2))，但 (N) 最大 2.5×10^5，不可行。

关键观察

1. 可达性保证：任意两点可达，说明图是强连通的。
2. 距离性质：
   • 如果 B 在 A 的东南或西北，则 dist(A,B) = 1
   • 否则，可能需要经过一个中转岛，它同时与 A 和 B 有直航边
3. 实际上，这个图是二维偏序关系图，最短路径长度通常很小（≤2 或 3？）

小规模思路（N ≤ 5000）

对每个点做一次 BFS，计算到其他点的距离和。
复杂度 (O(N \cdot (N+E)))，边数最多 (O(N^2))，但 N=5000 时可能勉强（优化后可过小数据）。

大规模思路（N ≤ 2.5×10^5）

需要 (O(N \log N)) 或 (O(N \sqrt{N})) 算法。

可能方法：

• 利用二维偏序，用扫描线 + 数据结构预处理每个点的“邻居”信息
• 发现 dist(A,B) 多数为 1 或 2，少数为 3
• 可以分类讨论：
  • 如果 B 在 A 的东南或西北 → dist=1
  • 否则，检查是否存在一个岛 C，使得 A→C 和 C→B 都是直航（dist=2）
  • 如果还不存在，则 dist=3（保证连通，所以最大为 3？）

这样，问题转化为二维平面上点的计数问题，用树状数组/线段树做区域查询。

算法步骤（优化思路）

1. 对每个点 P，将其他点分为：
   • 第一象限（右下）相对于 P：dist=1
   • 第三象限（左上）相对于 P：dist=1
   • 其余点：尝试找中转点
2. 用扫描线预处理每个点能直达的点集
3. 计算 dist=2 的情况：即存在一个中介点同时与起点和终点直航
4. 若还不通，则 dist=3（题目保证连通，所以最多 3 跳）

这样对每个点，答案 =
(距离1的点数 × 1) + (距离2的点数 × 2) + (距离3的点数 × 3)

算法标签

• 二维偏序
• 扫描线
• BFS（小数据）
• 图的最短路和
• 几何化图论

参考实现（小数据 BFS 版本）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    vector<pair<int, int>> islands(N);
    for (int i = 0; i < N; i++) {
        cin >> islands[i].first >> islands[i].second;
    }
    
    // 建图：邻接表
    vector<vector<int>> adj(N);
    for (int i = 0; i < N; i++) {
        int r1 = islands[i].first, c1 = islands[i].second;
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            int r2 = islands[j].first, c2 = islands[j].second;
            if ((r1 < r2 && c1 < c2) || (r1 > r2 && c1 > c2)) {
                adj[i].push_back(j);
            }
        }
    }
    
    // BFS 求所有点对最短距离和
    for (int start = 0; start < N; start++) {
        vector<int> dist(N, -1);
        queue<int> q;
        dist[start] = 0;
        q.push(start);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        
        int total = 0;
        for (int i = 0; i < N; i++) {
            if (i != start) total += dist[i];
        }
        cout << total << "\n";
    }
    
    return 0;
}