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>

上次修改时间 2017-05-22

相关日志