POI 1998 相交的矩形 Rectangles

很明顯,這個題是求連通塊的個數。關鍵在於正確判斷兩個矩形相交。

我們知道,在一維的數軸上,兩個區間[a,b] [c,d] (a<=b),這兩個區間相交的充分必要條件是c<=b。對於題中所述的邊平行於座標軸的矩形,我們需要分別判斷x軸方向和y軸方向都相交,那麼這個矩形一定相交。

假設我們對於給定的兩個矩形A,B,A矩形的左下點座標爲(A.x1,A.y1),右上點座標(A.x2,A.y2),同理B點,判斷這兩個矩形相交,要分爲以下四種情況

  • 情況1:A在B左下 (A.x1 <= B.x1 且 A.y1 <= B.y1)

    • 該情況下兩個矩形相交的條件是 (B.x1<=A.x2 且 B.y1<=A.y2)
  • 情況2:A在B左上 (A.x1 <= B.x1 且 A.y1 >= B.y1)

    • 該情況下兩個矩形相交的條件是 (B.x1<=A.x2 且 A.y1<=B.y2)
  • 情況3:A在B右下 (A.x1 >= B.x1 且 A.y1 <= B.y1)

    • 該情況下兩個矩形相交的條件是 (A.x1<=B.x2 且 B.y1<=A.y2)
  • 情況4:A在B左上 (A.x1 >= B.x1 且 A.y1 >= B.y1)

    • 該情況下兩個矩形相交的條件是 (A.x1<=B.x2 且 A.y1<=B.y2)

根據以上四種情況分類討論,可以判斷A和B是否相交。但是以上方法會造成一個遺漏,就是按題意如果兩個矩形只有一個公共點,不能算作相交。對於這種特殊判斷,需要排除只有一個交點的狀態。

  • 情況1:A在B左下 (A.x1 <= B.x1 且 A.y1 <= B.y1)

    • 該情況下要排除(A.x2==B.x1 且 A.y2==B.y1)的狀態
  • 情況2:A在B左上 (A.x1 <= B.x1 且 A.y1 >= B.y1)

    • 該情況下要排除(A.x2==B.x1 且 A.y1==B.y2)的狀態
  • 情況3:A在B右下 (A.x1 >= B.x1 且 A.y1 <= B.y1)

    • 該情況下要排除(A.x1==B.x2 且 A.y2==B.y1)的狀態
  • 情況4:A在B左上 (A.x1 >= B.x1 且 A.y1 >= B.y1)

    • 該情況下要排除(A.x1==B.x2 且 A.y1==B.y2)的狀態

根據以上方法,我們就可以判斷每對矩形是否相交了。接下來要求出所有的連通塊,由於N多達7000,一般的O(N^2)的廣搜會超時,需要用並查集求連通塊。

初始時把每個矩形作爲單獨的一個集合,如果兩個矩形相交,合併這兩個矩形所屬的集合,最後統計剩餘的集合數,就是連通塊的個數。這樣時間複雜度雖然還近似是O(N^2),但是會減少搜索時許多無用的操作,所以可以解決問題。

/* 
 * Problem: POI1998 pro
 * Author: Guo Jiabao
 * Time: 2008.12.6 18:05:22
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=7001;

class tUFS
{
    public:
        int F[MAXN];
        int size;
        tUFS(int sz) : size(sz)
        {
            for (int i=1;i<=sz;i++)
                F[i]=-i;
        }
        int findroot(int a)
        {
            int r,t;
            for (r=a;F[r]>0;r=F[r]);
            for (;F[a]>0;a=t)
            {
                t=F[a];
                F[a]=r;
            }
            return r;
        }
        int getroot(int a)
        {
            return -F[findroot(a)];
        }
        void Union(int a,int b)
        {
            F[findroot(a)]=findroot(b);
        }
        bool judge(int a,int b)
        {
            return F[findroot(a)]==F[findroot(b)];
        }
};

struct rect
{
    int x1,y1,x2,y2;
};

int N,Ans;
rect R[MAXN];
bool H[MAXN];
tUFS *U;

void init()
{
    int i;
    freopen("pro.in","r",stdin);
    freopen("pro.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
        scanf("%d%d%d%d",&R[i].x1,&R[i].y1,&R[i].x2,&R[i].y2);
    U=new tUFS(N);
}

bool across(rect &A,rect &B)
{
    if (A.x1 <= B.x1) // left
    {
        if (A.y1 <= B.y1) // down
            return (B.x1<=A.x2 && B.y1<=A.y2 && !(A.x2==B.x1 && A.y2==B.y1));
        else
            return (B.x1<=A.x2 && A.y1<=B.y2 && !(A.x2==B.x1 && A.y1==B.y2));
    }
    else
    {
        if (A.y1 <= B.y1)
            return (A.x1<=B.x2 && B.y1<=A.y2 && !(A.x1==B.x2 && A.y2==B.y1));
        else
            return (A.x1<=B.x2 && A.y1<=B.y2 && !(A.x1==B.x2 && A.y1==B.y2));
    }
}

void solve()
{
    int i,j;
    for (i=1;i<=N;i++)
        for (j=1;j<=i-1;j++)
            if (across(R[i],R[j]))
                if (!U->judge(i,j))
                    U->Union(i,j);
    for (i=1;i<=N;i++)
        H[U->getroot(i)]=true;
    for (i=1;i<=N;i++)
        if (H[i])
            Ans++;
}

int main()
{
    init();
    solve();
    printf("%d",Ans);
    return 0;
}
<h2><span class="mw-headline">相交的矩形 </span></h2>

在一個平面上畫了n個矩形。每一個矩形有平行於座標軸的邊和整數的頂點座標。 我們定義一個如下的塊:
<ol>
    <li>每一個矩形是一個塊,</li>
    <li>如果兩個不同的塊有一個公共段那麼它們組成一個新的塊,否則我們說這些塊是獨立的。</li>
</ol>
圖1的矩形組成了兩個獨立的塊。

<a class="image" title="Image:Poi pro 1.gif" href="http://www.ruvtex.cn/wiki/Image:Poi_pro_1.gif"><img src="http://www.ruvtex.cn/mw/images/0/00/Poi_pro_1.gif" alt="Image:Poi pro 1.gif" width="134" height="148" /></a>

圖2的矩形組成了一個塊。

<a class="image" title="Image:Poi pro 2.gif" href="http://www.ruvtex.cn/wiki/Image:Poi_pro_2.gif"><img src="http://www.ruvtex.cn/mw/images/0/05/Poi_pro_2.gif" alt="Image:Poi pro 2.gif" width="134" height="149" /></a>

任務

寫一個程序:
<ol>
    <li>從文件中讀取矩形數和它們頂點的座標;</li>
    <li>找出各個由矩形組成的獨立塊的數目;</li>
    <li>把結果寫到文件中。</li>
</ol>
輸入

在輸入文件的首行有一個整數n(1 &lt;= n &lt;=7000),它是矩形數。在接下來的n行裏有矩形的座標,每一個矩形被四個數描述:左下角頂點的座標x,y和右上角頂點座標。所有這些座標都是不大於10000的非零整數。

輸出

在文件的首行應該寫下一個整數-被所給矩形形成的獨立塊的數量。

樣例輸入
<pre>9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1</pre>
樣例輸出
<pre>2</pre>

相關日誌