《算法竞赛入门经典（第2版）》习题3-10 盒子 (Box, ACMICPC NEERC 2004, UVa1587)

《算法竞赛入门经典（第2版）》习题3-10 盒子 (Box, ACM/ICPC NEERC 2004, UVa1587)

给定6个矩形的长和宽wi和hi(1<=wi,hi<=10000)，判断它们能否构成长方体的6个面。 【输入】 包含若干个测试样例，每个样例包含6行，每行包括两个整数w和h，表示长方形的宽和高。(1<=w,h<=10000) 【输出】 对每一个样例，输出‘POSSIBLE’表示能够构成长方体，输出‘IMPOSSIBLE’表示不可以。

样例输入

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

样例输出

POSSIBLE IMPOSSIBLE

分析

此程序的关键在于，先要对这6个长方形排序，每个长方形的长度wi为第一关键字，若wi相等，高度hi为第2关键字。排序之后，判断6个长方形的关系就变得很简单了。设6个长方形为0-5，那么首先要保证两两相等，0==1，且2==3，且4==5。然后，在两两相等的前提下，0的短边等于2的短边，且0的长边等于4的短边，且2的长边等于4的长边。以上条件全部满足，则能够构成长方体；若有一项不满足，则无法构成。

代码

#include <stdio.h> #include <string.h> #include <ctype.h> #include <time.h> struct { int a, b; }rec[10], temp; int a, b, i, j, ans; int main() { while((scanf("%d%d", &a, &b))!=EOF){ i = 0; rec[i].a = a; // 输入第1个矩形 rec[i].b = b; if(a>b) {int temp = rec[i].a; rec[i].a = rec[i].b; rec[i].b = temp;} // 确保a<=b for(i=1;i<=5;i++){ // 输入接下来的5个矩形 scanf("%d%d", &rec[i].a, &rec[i].b); if(rec[i].a>rec[i].b) {int temp = rec[i].a; rec[i].a = rec[i].b; rec[i].b = temp;} // 确保a<=b } // 对6个矩形从小到大排序，第1关键字a，第2关键字b for(i=0;i<5;i++) for(j=i+1;j<6;j++) { if(rec[i].a > rec[j].a){temp=rec[i];rec[i]=rec[j];rec[j]=temp;} // 第1关键字a else if(rec[i].a == rec[j].a){ if(rec[i].b > rec[j].b){temp=rec[i];rec[i]=rec[j];rec[j]=temp;} // 第2关键字b } } ans = 1; // 能否构成长方体： for(i=0;i<6;i+=2){ if((rec[i].a != rec[i+1].a) || (rec[i].b != rec[i+1].b)){ // 首先，6个长方形要两两相等 ans = 0; break; } // 其次，0号的短边=2号的短边，且0号长边=4号短边，且2号长边=4号长边 if((rec[0].a != rec[2].a) || (rec[0].b != rec[4].a) || (rec[2].b != rec[4].b)){ ans = 0; break; } } if(ans==1) printf("POSSIBLE\n"); else printf("IMPOSSIBLE\n"); } return 0; }