首页 > 代码库 > POJ 1231 The Alphabet Game

POJ 1231 The Alphabet Game

【题意简述】:输入的k和p,k表示有几个字母,也就是输入有几行,p表示每个字母有几个,是以坐标的形式出现的(x,y).现在让我们将相同的字母划分在一个矩形块中,问能否实现。

【分析】:唉,低级失误!!!记住!积累!

/*
	Date:  2014/11/04
	Time:  21:38
	By	:  VID
	
	Attention:
		坐标的建立是理解这个问题,梳理思路的关键。
		我的坐标系是x轴指向右,y轴指向下,就像题中的图一样! 
*/
// 228K 0ms

#include<iostream>
using namespace std;

#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define Inf 1000000000

int lef[27],righ[27],up[27],under[27];

bool check(int n)
{
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			if(i == j) continue;
			if(((lef[j]>=lef[i]&&lef[j]<=righ[i]) || (righ[j]<=righ[i]&&righ[j]>=lef[i]))
			&&((up[j]>=up[i]&&up[j]<=under[i]) || (under[j]<=under[i]&&under[j]>=up[i])))
			
			return 0;
		}
	}
	return 1;
}

int main()
{
	int t,k,p;
	int x,y;
	cin>>t;
	while(t--)
	{
		cin>>k>>p;
		for(int i = 0;i<k;i++)
		{
			int ll = Inf,rr = 0,uup = Inf,un = 0;
			for(int j = 0;j<p;j++)
			{
				cin>>x>>y;
				ll = Min(ll,x),rr = Max(rr,x),uup = Min(uup,y),un = Max(un,y);
			}
			lef[i] = ll,righ[i] = rr,up[i] = uup,under[i] = un;
		}
		
		for(int i = 0;i<k;i++)
		{
			for(int j =0 ;j<k;j++)
			{
				if(i == j) continue;
				if(lef[i] > lef[j] && lef[i]<righ[j]) lef[i] = lef[j];
				if(righ[i] < righ[j] && righ[i]>lef[j]) righ[i] = righ[j];
				if(up[i] > up[j] && up[i] < under[j])  up[i] = up[j];
				if(under[i] < under[j]&& under[i]>up[j]) under[i] = under[j];
			}
		}
		if(check(k)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;;
	}
	return 0;
}


POJ 1231 The Alphabet Game