题目链接:Click here~~
题意:
在三维空间内,有n个长方体,棱都与坐标轴平行。给出一些关系,问是否可能,若可能,输出其中的一种。
关系有两种:
1、某两个长方体相交。
2、某个长方体的所有点的某一维的坐标完全小于另一个长方体的任意一点。
解题思路:
首先,对于棱与坐标轴平行的长方体,在某一维中,它里面的点可以看做包含在长方体的两个平面内,且点的坐标正好在两个平面的坐标的区间内。
而题目让我们所求的,正是坐标区间,于是我们可以求平面的坐标来得到。
然后,考虑相交的情况,我们可以得出:若某两个长方体相交,当且仅当每一维中,其中的一个长方体的面插进了另一个长方体的内部。
我们以 y 轴为例,画出上图,题中的信息只给出了A和B相交,但是我们不知道谁是A,谁是B,所以我们只能得到一些与A、B无关的关系:
A1<B2、B1<A2,即一个长方体的左面一定小于另一个长方体的右面。
于是我们可以根据这些偏序关系,把长方体的6个面抽象成6个点,对三维分别作拓扑排序,其中每一维只与2个面有关。
#include <queue>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 2005
struct T
{
int v,next;
}E[3][N*100];
struct TT
{
int head,rd,dep;
}V[3][N];
int top[3],ans,n,m;
void Add_Edge(int k,int u,int v)
{
E[k][top[k]].v = v;
E[k][top[k]].next = V[k][u].head;
V[k][u].head = top[k]++;
++V[k][v].rd;
}
bool Top_Sort(int k)
{
queue<int> Q;
for(int i=1;i<=n;i++)
if(V[k][i].rd == 0)
Q.push(i);
int cnt = 0;
while(!Q.empty())
{
++cnt;
int p = Q.front();
for(int i=V[k][p].head;i!=NULL;i=E[k][i].next)
{
int q = E[k][i].v;
--V[k][q].rd;
if(V[k][q].rd == 0)
{
Q.push(q);
V[k][q].dep = V[k][p].dep + 1;
}
}
Q.pop();
}
return cnt == n;
}
int main()
{
int u,v,nn,ncase=0;
char cmd;
while(~scanf("%d%d%*c",&nn,&m),nn)
{
memset(V,0,sizeof(V));
top[0] = top[1] = top[2] = 1;
n = 2*nn;
for(int k=0;k<3;k++)
for(int i=1;i<=nn;i++)
Add_Edge(k,i,i+nn);
while(m--)
{
scanf("%c%d%d%*c",&cmd,&u,&v);
if(cmd == 'I')
{
for(int k=0;k<3;k++)
{
Add_Edge(k,u,v+nn);
Add_Edge(k,v,u+nn);
}
}
else
Add_Edge(cmd-'X',u+nn,v);
}
printf("Case %d: ",++ncase);
if(!Top_Sort(0) || !Top_Sort(1) || !Top_Sort(2))
puts("IMPOSSIBLE\n");
else
{
puts("POSSIBLE");
for(int i=1;i<=nn;i++)
printf("%d %d %d %d %d %d\n",V[0][i].dep,V[1][i].dep,V[2][i].dep,V[0][i+nn].dep,V[1][i+nn].dep,V[2][i+nn].dep);
puts("");
}
}
return 0;
}
分享到:
相关推荐
hdu ACM 各种排序
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu杭电所有题目按照ac数量排序,python分析
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类