1224 - God’s Palace
Time Limit : 2 Second
Memory Limit : 128 MB
- Someone thinks that there is a god in the world, he lives in a sky palace. The palace is about as large as a 500000m*500000m*500000m cubic space. And there are many magic boxes in the palace. We know the size of one magic box is 1m*1m*1m and all the edge of the box are paralleled the X-axis,the Y-axis or Z-axis. Maybe there are two boxes share a same face, we think that they belong to the same part.
Now, what you should do is to tell me the size of the largest part, and how many such sized part. At first, we will tell you the positions of all the boxes.
- In the first line there is a Integer T(1<=T<=10), which means the number of test case in the palace. The other lines are the T test cases.
For each test case, there is an Integer N(1<=N<=1000000), which means the number of boxes in the palace, then N lines follows, each line contains 3 Integers Xi,Yi,Zi(0<=Xi,Yi,Zi<500000), means the position of the i-th boxes’s center.
- For each test case, you should output one line, contains 2 Intergers, the first one is the size of the largest part and the second one is the number of such sized boxes.
- sample input
2 2 0 0 0 0 1 1 2 0 0 0 0 0 1
- sample output
1 2 2 1
- Sempr, HUST Programming Contest 2007