algorithm - RECTNG1 spoj 中的 TLE 关于查找由具有整数坐标的矩形形成的单独 block 的数量的问题

Question

我正在努力解决 the SPOJ problem on rectangles .问题陈述:

There are n rectangles drawn on the plane. Each rectangle has sides parallel to the coordinate axes and integer coordinates of vertices. We define a block as follows:

• each rectangle is a block,

• if two distinct blocks have a common segment then they form the new block otherwise we say that these blocks are separate.

Write a program that for each test case:

• reads the number of rectangles and coordinates of their vertices;
• finds the number of separate blocks formed by the rectangles;
• writes the result to the standard output.

Input:

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

In the first line of a test case there is an integer n, 1 <= n <= 7000, which is the number of rectangles. In the following n lines there are coordinates of rectangles. Each rectangle is described by four numbers: coordinates x, y of the bottom-left vertex and coordinates x, y of the top-right vertex. All these coordinates are non-negative integers not greater than 10000.

Output:

For each test case you should output one line with the number of separate blocks formed by the given rectangles.

我的方法:

1. 检查每对矩形 r_i 和 r_j 是否基于该集合的邻接矩阵 mat[i][j ] 和 mat[j][i] 分别为 true 或 false

2. 然后在构建的图上运行 DFS 以计算连接路径的数量。此计数将代表单独 block 的数量。

由于矩形的数量最多为 7000，所以看每一对都不会超过 10^7。我仍然得到 TLE(超出时间限制)。

如何更有效地解决这个问题？

void comp() {
    list.clear();

    scanI(n);

    REP(i,1,n) {
         Rec rec;
        scanI(rec.p);
        scanI(rec.q);
        scanI(rec.r);
        scanI(rec.s);
        list.pb(rec);
    }
    REP(i,0,list.size()-2){
        Rec rec = list[i];
        p = rec.p;
        q = rec.q;
        r = rec.r;
        s = rec.s;

        REP(j,i+1,list.size()-1) {
            Rec m = list[j];
            a = m.p;
            b = m.q;
            c = m.r;
            d = m.s;
            if(!isSeparate()) {
                eList[i].pb(j); //adjacency list for rec_i
                eList[j].pb(i);//adjacency list for rec_j
            }
        }
    }

    int cnt=0;
    REP(i,0,n-1) {
        if(!vis[i]){
            cnt++;
            dfs(i);
        }
    }
    printf("%d\n",cnt);
}

bool isSeparate(){
    if(s<b || d<q || r<a || c<p) return true;
    if((r==a && q==d)||(c==p && b==s)||(a==r && b==s)||(p==c && q==d)) return true;
    else return false;
}

void dfs(int s) {
    cout<<"Visited : "<<s<<endl;
    if(vis[s]) return;
    vis[s] = true;
    REP(i,0,eList[s].size()-1){
        if(!vis[eList[s][i]]){
            dfs(eList[s][i]);
        }
    }
}

Answer 1

我想到了一些更多的算法改进。

使用快速联合/查找数据结构，而不是构建图的邻接表表示。然后，如果一个矩形与另一个矩形相交，您可以立即停止——没有必要继续针对目前看到的所有其他矩形进行测试。有了这个，大多数矩形与大多数其他矩形相交的问题实例将很快得到解决。

仍然需要有效地处理大多数矩形与很少或没有其他矩形相交的问题实例。一些观察:

• 只有当垂直和水平范围重叠时，一个矩形才能重叠另一个矩形。
• 如果我们有 n 个不重叠的矩形，这些矩形以某个 h*w 网格的网格点为中心，则必须满足 min(h, w) <= sqrt(n)。

假设问题实例具有上面第二个要点的形式——一个由非重叠矩形组成的 h*w 网格，其中 h*w = n 但 h 和 w 否则未知。在处理每个矩形时，将其垂直范围插入到支持快速区间点查询的数据结构中，例如区间树或线段树，并将其水平范围插入另一个此类数据结构中。使用此信息的明显方法——通过查找垂直重叠当前矩形的所有矩形，并查找水平重叠的所有矩形，然后将这两个列表相交——并没有带来太多速度优势，因为其中之一这些 list 可能会很长。您可以做的是简单地选择这两个列表中较短的一个并测试其中的每个矩形(和以前一样，一旦检测到重叠就停止)。这很快，因为我们知道较短的列表最多可以包含 sqrt(7000) 个矩形。

我还没有证明非重叠矩形网格是该算法的真正最坏情况，但我相信上述方法在任何情况下都会很快奏效。