盒子(Box)

Box

Time limit: 3.000 seconds

Ivan works at a factory that produces heavy machinery. He hasa simple job -- he knocks up wooden boxes of different sizesto pack machinery for delivery to the customers. Each boxis a rectangular parallelepiped. Ivan uses six rectangular wooden palletsto make a box. Each pallet is used for one side of the box.

Joe delivers pallets for Ivan. Joe is not very smart andoften makes mistakes -- he brings Ivan pallets that do not fittogether to make a box. But Joe does not trust Ivan. It alwaystakes a lot of time to explain Joe that he has made a mistake.Fortunately, Joe adores everything related to computers and sincerelybelieves that computers never make mistakes. Ivan has decided touse this for his own advantage. Ivan asks you to writea program that given sizes of six rectangular palletstells whether it is possible to make a box out of them.

Input 

Input file contains several test cases. Each of them consists of six lines. Each line describes one pallet andcontains two integer numbers w and h ( 1w,h10 000) --width and height of the pallet in millimeters respectively.

Output 

For each test case, print one output line. Write a single word ` POSSIBLE' to the output file if it is possibleto make a box using six given pallets for its sides. Write a single word` IMPOSSIBLE' if it is not possible to do so.

Sample Input 

1345 2584
2584 683
2584 1345
683 1345
683 1345
2584 683
1234 4567
1234 4567
4567 4321
4322 4567
4321 1234
4321 1234
  

Sample Output 

POSSIBLE
IMPOSSIBLE
  

【分析】

      将长宽不同的矩形放在不同的数组，不同矩形的数量大于3时，将其余不同的矩形均放在同一个数组中，具体实现可查看源代码。
对于一个长方体来说，它最多可由3个不同的矩形组成即3个对面均不同，此外，它还可由2个相同的上下底面和4个相同的侧面组成，
另外还有一种情况是6个面均相同即正方体，也是特殊的长方体。
首先创建4个二维数组，数组的第一行第一列的值表示一个矩形的宽，第一行第二列的值表示这个矩形的高；同样地，第二行第一列、第二列表示第二矩形……（规定，高>宽）将不同矩形保存到不同数组。假设一个矩形与前3个数组内的矩形（前提：3个数组内均有矩形）均不同则都放在第4个数组。其实，前3个数组保存的是长方体的对面。
将输入的6个矩形保存完毕后，判断第四个数组内是否有元素，如果第第个数组有元素的话，说明这6个面不能构成长方体。（因为一个长方体最多由3个不同的矩形构成）当前3个数组中有个数组内的元素个数为奇数，同样也不能构成长方体。（想一想就知道为什么了）（如果均不为奇数，那么3个数组元素的个数可能有以下组合：[6,0,0]、[2,2,2]、[2,4,0]、[4,2,0]，此外并无其他的了）
接下来通过，前3个数组内的元素个数进行分类讨论：
1、当第一个数组的元素个数为6，说明6个矩形均相同，能构成一个长方体；
2、数组元素个数均为2的情况；（将不同的宽高加入到一个不含重复元素的数组中，通过判断数组的元素个数来分析是否符合条件，当出现元素个数为3时，说明有3个不同的面并且可以形成3个对面组成长方体）
3、数组元素个数分别为2、4、0或者4、2、0（当出现这种情况时，长方体的上下地面均为正方形，如果不是正方形说明不能构成长方体）

用java语言编写程序，代码如下：

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while(input.hasNext()) {
			int[][] a = new int[6][2]; int a0 = 0;
			int[][] b = new int[6][2]; int b0 = 0;
			int[][] c = new int[6][2]; int c0 = 0;
			int[][] d = new int[6][2]; int d0 = 0;
			
			for(int i = 0; i < 6; i++) {
				int w = input.nextInt();
				int h = input.nextInt();
				
				if(w > h) {
					int t = w;
					w = h;
					h = t;
				}
				
				if(a0 == 0 || w == a[a0 - 1][0] && h == a[a0 - 1][1]) {
					a[a0][0] = w;
					a[a0][1] = h;
					a0++;
				}
				else if(b0 == 0 || w == b[b0 - 1][0] && h == b[b0 - 1][1]) {
					b[b0][0] = w;
					b[b0][1] = h;
					b0++;
				}
				else if(c0 == 0 || w == c[c0 - 1][0] && h == c[c0 - 1][1]) {
					c[c0][0] = w;
					c[c0][1] = h;
					c0++;
				}
				else {
					d[d0][0] = w;
					d[d0][1] = h;
					d0++;
				}
			}
			
			if(d0 != 0 || a0 % 2 == 1 || b0 % 2 == 1 || c0 % 2 == 1)
				System.out.println("IMPOSSIBLE");
			else {
				if(a0 == 6)
					System.out.println("POSSIBLE");
				else if(a0 == 2 && b0 == 2 && c0 == 2) {
					if(a[0][0] == a[0][1] || b[0][0] == b[0][1] || c[0][0] == c[0][1])
						System.out.println("IMPOSSIBLE");
					else {
						int[] e = new int[6];
						int start = 0;
						e[start++] = a[0][0];
						if(a[0][1] != e[0])
							e[start++] = a[0][1];
						
						start = add(e, start, b[0][0]);
						start = add(e, start, b[0][1]);
						start = add(e, start, c[0][0]);
						start = add(e, start, c[0][1]);
						if(start == 3)
							System.out.println("POSSIBLE");
						else
							System.out.println("IMPOSSIBLE");
					}
					
				} else if(a0 == 2 && b0 == 4) {
					if(a[0][0] == a[0][1] && (a[0][0] == b[0][0] || a[0][0] == b[0][1]))
						System.out.println("POSSIBLE");
					else
						System.out.println("IMPOSSIBLE");
				} else if(a0 == 4 && b0 == 2) {
					if(b[0][0] == b[0][1] && (b[0][0] == a[0][0] || b[0][0] == a[0][1]))
						System.out.println("POSSIBLE");
					else
						System.out.println("IMPOSSIBLE");
				}
				else
					System.out.println("IMPOSSIBLE");
			}
		}
	}
	
	public static int add(int[] e, int start, int temp) {
		for(int x = 0; x < start; x++) {
			if(temp == e[x])
				return start;
		}
		e[start++] = temp;
		return start;
	}
}