UVa 1587 Box

题意：给出6个矩形的长和宽，问是否能够构成一个长方体

先假设一个例子

2 3

3 4

2 3

3 4

4 2

排序后

2 3

3 4

4 2

如果要构成一个长方体的话，有3对面是一样的先判断这个成立了，再判断能否构成长方体假设现在剩下的面就为

2 3 （第一个面）

3 4 （第二个面）

4 2 （第三个面）

发现是首尾相接的，即为只需要判断三次，第一个面的长或者宽或者两者都在第二个面出现，第一个面的长或者宽或者两者都在第三个面出现，第二个面的长或者宽或者两者都在第三个面出现，如果三个条件都满足的话，就构成了

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>  
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int x,y;
10 } a[10];
11 
12 int cmp(node n1,node n2)
13 {
14     if(n1.x!=n2.x)
15     return n1.x<n2.x;
16     else return n1.y<n2.y;
17 }
18 
19 int main()
20 {
21     int i,j,ans;
22     while(scanf("%d",&a[1].x)!=EOF)
23     {
24         scanf("%d",&a[1].y);
25         for(i=2;i<=6;i++)
26         scanf("%d %d",&a[i].x,&a[i].y);
27         
28         for(i=1;i<=6;i++)
29         {
30             if(a[i].x>a[i].y) swap(a[i].x,a[i].y);
31         }
32         sort(a+1,a+6+1,cmp);
33         
34     //    for(i=1;i<=6;i++)
35     //    printf("%d %d
",a[i].x,a[i].y);
36     
37         ans=0;
38         int flag=1;
39         if(a[1].x==a[2].x&&a[1].y==a[2].y&&a[3].x==a[4].x&&a[3].y==a[4].y&&a[5].x==a[6].x&&a[5].y==a[6].y)
40         {
41             if(a[1].x==a[3].x||a[1].x==a[3].y||a[1].y==a[3].x||a[1].y==a[3].y) ans++;
42             if(a[1].x==a[5].x||a[1].x==a[5].y||a[1].y==a[5].x||a[1].y==a[5].y) ans++;
43             if(a[3].x==a[5].x||a[3].x==a[5].y||a[3].y==a[5].x||a[3].y==a[5].y) ans++;
44             if(ans<3) flag=0;
45             
46         }
47         else
48         flag=0;
49         
50         if(flag) printf("POSSIBLE
");
51         else printf("IMPOSSIBLE
");        
52     }
53     return 0;
54 }

View Code

不过后来又想到一个反例= =正想着改的时候---居然过了= = 反例是

12 34

34 12

12 34

34 12

12 34

这应该不能构成吧--可是程序输出的是能 ----不懂= =