现有n个矩形，任何两个矩形恰好相交于两点，且任何三个矩阵不相交于同一点，请计算出n个矩形之间相交的点有多少个？ image.png 输入描述 一行，一个整数n，代表矩形的个数。（1≤n≤10000） 输出描述 一个整数，n代表矩形之间相交的点数。c++

这个问题可以用图论中的“并查集”数据结构来解决。我们可以构建一个点-边图，其中每个矩形的两个边界点对应为图中的两个节点，每对相交的矩形会连接这两个对应的节点。因为任何三个矩形不相交于同一点，所以任意两条边都不交叉。使用并查集维护每个集合（由一个矩形的所有边界点构成）内的点数，当发现一对边界点属于同一集合时（即它们所在的矩形相交），我们只需合并这两个集合，并增加计数。

以下是C++的一个简要实现：

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

class UnionFind {
private:
    vector<int> parent;
    int setSize;

public:
    UnionFind(int n) {
        parent.resize(n);
        setSize = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int findSet(int node) {
        if (parent[node] == node) {
            return node;
        }
        return parent[node] = findSet(parent[node]);
    }

    void unionSet(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            if (setSize[a] < setSize[b]) {
                swap(a, b);
            }
            parent[b] = a;
            setSize[a]--;
        }
    }

    int sizeOfSet(int node) {
        return setSize[findSet(node)];
    }
};

int countIntersectionPoints(int n) {
    UnionFind uf(n * 4); // 因为每个矩形有4个边界点
    int intersectionCount = 0;
    for (int i = 0; i < n; i++) {
        // 对于每个矩形的四个边界点...
        for (int j = i + 1; j < n; j++) {
            // 检查是否相交...
            if (uf.findSet(i*2) != uf.findSet(j*2+1) && uf.findSet(i*2+1) != uf.findSet(j*2)) { 
                uf.unionSet(i*2, j*2+1); // 相交则合并集合
                uf.unionSet(i*2+1, j*2); // 相交则合并集合
                intersectionCount++; // 计数加一
            }
        }
    }
    return intersectionCount;
}

int main() {
    int n;
    cin >> n;
    cout << countIntersectionPoints(n) << endl;
    return 0;
}