Box Relations
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1042 Accepted Submission(s): 389
Special Judge
Problem Description
There are n Boxes C1,C2,...,Cn in 3D space. The edges of the Boxes are parallel to the
x,y or z-axis. We provide some relations of the Boxes,and your task is to construct a set of Boxes satisfying all these relations.
There are four kinds of relations (1 <= i,j <= n,i is different from j):
There are four kinds of relations (1 <= i,j <= n,i is different from j):
- I i j: The intersection volume of Ci and Cj is positive.
- X i j: The intersection volume is zero,and any point inside Ci has smaller
x-coordinate than any point inside Cj.
- Y i j: The intersection volume is zero,and any point inside Ci has smaller
y-coordinate than any point inside Cj.
- Z i j: The intersection volume is zero,and any point inside Ci has smaller z-coordinate than any point inside Cj.
Input
There will be at most 30 test cases. Each case begins with a line containing two integers
n (1 <= n <= 1,000) and R (0 <= R <= 100,000),the number of Boxes and the number of relations. Each of the following
R lines describes a relation,written in the format above. The last test case is followed by
n=R=0,which should not be processed.
Output
For each test case,print the case number and either the word POSSIBLE or IMPOSSIBLE. If it's possible to construct the set of Boxes,the
i-th line of the following n lines contains six integers x1,y1,z1,x2,y2,z2, that means the
i-th Box is the set of points (x,y,z) satisfying x1 <= x <= x2,y1 <= y <= y2,z1 <= z <= z2. The absolute values of
x1,z2 should not exceed 1,000,000.
Print a blank line after the output of each test case.
Print a blank line after the output of each test case.
Sample Input
3 2 I 1 2 X 2 3 3 3 Z 1 2 Z 2 3 Z 3 1 1 0 0 0
Sample Output
Case 1: POSSIBLE 0 0 0 2 2 2 1 1 1 3 3 3 8 8 8 9 9 9 Case 2: IMPOSSIBLE Case 3: POSSIBLE 0 0 0 1 1 1
Source
2009 Asia Wuhan Regional Contest Hosted by Wuhan University
题意：
在3维空间内，有n个长方体，棱都与坐标轴平行。给出1些关系，问是不是可能，若可能，输出其中的1种。
关系有两种：
1、I:两个长方体有相交的体积。
2、X或Y或Z：某个长方体的所有点的某1维（X或Y或Z）的坐标完全小于另外一个长方体的任意1点。
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
const int N = 2005;
vector<int>mapt[3][N];
int in[3][N],v[3][N],n;
void init()
{
for(int i=0;i<3;i++)
for(int j=1;j<=n*2;j++)
in[i][j]=v[i][j]=0,mapt[i][j].clear();
for(int i=0;i<3;i++)//坐标X,Y,Z
for(int j=1;j<=n;j++)//盒子j,用两个点表示，点j与点j+n
{
in[i][j+n]++; mapt[i][j].push_back(j+n); //点j的坐标比相应的点j+n坐标值小
}
}
int topeSort()
{
for(int i=0;i<3;i++)
{
int k=0;
queue<int>q;
for(int j=1;j<=n;j++)
if(in[i][j]==0)
q.push(j),v[i][j]=k++;
while(!q.empty())
{
int s=q.front(); q.pop();
int len=mapt[i][s].size();
for(int j=0; j<len; j++)
{
int tj=mapt[i][s][j];
in[i][tj]--;
if(v[i][s]+1>v[i][tj])
v[i][tj]=v[i][s]+1;
if(in[i][tj]==0)
q.push(tj),k++;
}
}
if(k!=n*2)
return 0;
}
return 1;
}
int main()
{
char ch[5];
int m,a,b,cas=0;
while(scanf("%d%d",&n,&m)>0&&n+m!=0)
{
init();
while(m--)
{
scanf("%s%d%d",ch,&a,&b);
if(ch[0]=='I')
{
for(int i=0;i<3;i++)
{
mapt[i][a].push_back(b+n); in[i][b+n]++;
mapt[i][b].push_back(a+n); in[i][a+n]++;
}
}
else if(ch[0]=='X')
mapt[0][a+n].push_back(b),in[0][b]++;
else if(ch[0]=='Y')
mapt[1][a+n].push_back(b),in[1][b]++;
else if(ch[0]=='Z')
mapt[2][a+n].push_back(b),in[2][b]++;
}
printf("Case %d: ",++cas);
if(topeSort()==0)
printf("IMPOSSIBLE
");
else
{
printf("POSSIBLE
");
for(int i=1;i<=n;i++)
{
printf("%d",v[0][i]);
for(int j=1;j<3;j++)
printf(" %d",v[j][i]);
for(int j=0;j<3;j++)
printf(" %d",v[j][i+n]);
printf("
");
}
}
printf("
");
}
}
