天梯赛练习 L3-006 迎风一刀斩 (30分) 几何关系

题目分析：

对于给出的两个多边形是否可以组成一个矩形，这里我们分以下几种情况讨论

1.首先对于给出的两个多边形只有3-3，3-4，3-5，4-4才有可能组成一个矩形，并且两个多边形只可能是旋转90，180，270，360度得到的，所以如果能满足两个多边形是由一个矩形切成的，则这两个多边形最多有一条斜边，其余边都和坐标轴平行

2.经过第一轮筛选之后，我们继续分析，对于3-3和3-5的情况，我们只要判断两个多边形的斜边与坐标轴构成的三角形是否全等就能判断是否是一个矩形切得，而对于3-4则有一些不同，其中的四边形可能是梯形也可能是矩形，如果是矩形则三角+矩形不可能是一个矩形，如果是梯形则判断两条斜边与坐标轴构成的直角三角形是否全等即可

对于最后一种4-4的情况的讨论分为三种：1.都有一条斜边，此时情况有点特殊，因为即使有一条斜边，有可能是两个直角梯形构成的但不是矩形的情况，所以需要额外讨论这两个直角梯形的直角腰是否相等并且两条斜边构成的直角三角形是否全等；2.都没有斜边，此时判断两个矩形是否有一条边相等即可；3.如果一个四边形有斜边一个没有则显然不能构成矩形，结束

代码：

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<stdio.h>

 4 #include<string.h>

 5 #include<cmath>

 6 #include<vector>

 7 using namespace std;

 8

 9 vector<int> a, b, c, d;

10 int n, m, m1;

11

12 int judge(){

13     if(m == 3 && m1 == 3 || m == 3 && m1 == 4 || m == 3 && m1 == 5 || m == 4 && m1 == 4) return 1;

14     return 0;

15 }

16

17 int judge1(int x){

18     if(x == 1){

19         int flag = -1; int app = 0;

20         for(int i = 0; i < m; i++){

21             if(a[i] != a[(i+1)%m] && b[i] != b[(i+1)%m]){

22                 if(flag == -1){

23                     app = 1; flag = i;    //以下都以i 和i+1

24                 }

25                 else return -1;

26             }

27         }

28         if(app == 0) return 15; return flag;

29     }else{

30         int flag = -1; int app = 0;

31         for(int i = 0; i < m1; i++){

32             if(c[i] != c[(i+1)%m1] && d[i] != d[(i+1)%m1]){

33                 if(flag == -1){

34                     app = 1; flag = i;    //以下都以i 和i+1

35                 }

36                 else return -1;

37             }

38         }

39         if(app == 0) return 15; return flag;

40     }

41 }

42

43 int main(){

44     scanf("%d", &n);

45     for(int i = 1; i <= n; i++){

46         scanf("%d", &m);

47         a.clear(); b.clear(); c.clear(); d.clear();

48         for(int j = 1; j <= m; j++){

49             int x, y; scanf("%d%d", &x, &y);

50             a.push_back(x); b.push_back(y);

51         }

52         scanf("%d", &m1);

53         for(int j = 1; j <= m1; j++){

54             int x, y; scanf("%d%d", &x, &y);

55             c.push_back(x); d.push_back(y);

56         }

57         if(m > m1){    //方便判断将边数少的的放在前面

58             swap(m, m1); swap(a, c); swap(b, d);

59         }

60         int f1 = judge(); int f2 = judge1(1); int f3 = judge1(2);

61         if(f1 == 1 && f2 >= 0 && f3 >= 0){    //先判断构成的两个多边形是否可能组成矩形 以及是否都只有一条斜边

62             if(m == 3 && m1 == 3 || m == 3 && m1 == 5){    //3-3 3-5的情况

63                 int r1 = abs(a[f2] - a[(f2+1)%m]); int l1 = abs(b[f2] - b[(f2+1)%m]);

64                 int r2 = abs(c[f3] - c[(f3+1)%m1]); int l2 = abs(d[f3] - d[(f3+1)%m1]);

65                 if(r1 == r2 && l1 == l2 || r1 == l2 && l1 == r2) printf("YES\n");

66                 else printf("NO\n");

67             }else if(m == 3 && m1 == 4){    //3-4

68                 if(f3 == 15) printf("NO\n");    //如果四边形没有斜边

69                 else{

70                     int r1 = abs(a[f2] - a[(f2+1)%m]); int l1 = abs(b[f2] - b[(f2+1)%m]);

71                     int r2 = abs(c[f3] - c[(f3+1)%m1]); int l2 = abs(d[f3] - d[(f3+1)%m1]);

72                     if(r1 == r2 && l1 == l2 || r1 == l2 && l1 == r2) printf("YES\n");

73                     else printf("NO\n");

74                 }

75             }else{    //4-4

76                 if(f2 == 15 && f3 == 15){    //都没有斜边

77                     int r1 = (a[0] - a[1])*(a[0] - a[1]) + (b[0] - b[1])*(b[0] - b[1]); int l1 = (a[2] - a[1])*(a[2] - a[1]) + (b[2] - b[1])*(b[2] - b[1]);

78                     int r2 = (c[0] - c[1])*(c[0] - c[1]) + (d[0] - d[1])*(d[0] - d[1]); int l2 = (c[2] - c[1])*(c[2] - c[1]) + (d[2] - d[1])*(d[2] - d[1]);

79                     if(r1 == l2 || r1 == r2 || l1 == r2 || l1 == l2) printf("YES\n");

80                     else printf("NO\n"

81                     );

82                 }else if(f2 != 15 && f3 != 15){    //都有斜边

83                     int r1 = abs(a[f2] - a[(f2+1)%m]); int l1 = abs(b[f2] - b[(f2+1)%m]);

84                     int r2 = abs(c[f3] - c[(f3+1)%m1]); int l2 = abs(d[f3] - d[(f3+1)%m1]);

85                     if(r1 == r2 && l1 == l2 || r1 == l2 && l1 == r2){

86                         int r1 = abs(a[(f2+2)%m] - a[(f2+3)%m]); int l1 = abs(b[(f2+2)%m] - b[(f2+3)%m]);

87                         int r2 = abs(c[(f2+2)%m] - c[(f3+3)%m1]); int l2 = abs(d[(f2+2)%m] - d[(f3+3)%m1]);

88                         if(r1 == r2 && l1 == l2 || r1 == l2 && l1 == r2) printf("YES\n");

89                         else printf("NO\n");

90                     }

91                     else printf("NO\n");

92                 }else{

93                     printf("NO\n");

94                 }

95             }

96         }else printf("NO\n");

97     }

98     return 0;

99 }

巴特西

天梯赛练习 L3-006 迎风一刀斩 (30分) 几何关系

最新文章

热门文章