POI 1998 相交的矩形 Rectangles

本文正體字版由OpenCC轉換

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

我們知道，在一維的數軸上，兩個區間[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

相關日誌