POI 1998 相交的矩形 Rectangles

This post is written in Chinese. Please consider using Google Translate

很明显,这个题是求连通块的个数。关键在于正确判断两个矩形相交。

我们知道,在一维的数轴上,两个区间[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>

Related posts