BestCoder Round #38

1001 Four Inages Strategy

题意：给定空间的四个点，判断这四个点是否能形成正方形

思路：判断空间上4个点是否形成一个正方形方法有很多，这里给出一种方法，在

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 struct node
 5 {
 6     __int64 x, y, z;
 7 };
 8 
 9 node points[4];　　// 存放四个点坐标
10 
11 __int64 dist(node a, node b) // 计算两点之间的距离
12 {
13     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
14 }
15 
16 bool isVertical(node a, node b) // 判断两个向量是否垂直
17 {
18     if (a.x * b.x + a.y * b.y + a.z * b.z == 0) return true;
19     return false;
20 }
21 
22 bool isSquare(node a, node b, node c, node& p) // 判断是否为等腰直角（成正方形的必要条件）
23 {
24     __int64 len1 = dist(a, b);
25     __int64 len2 = dist(a, c);
26 
27     node d, e;
28     d.x = b.x - a.x;
29     d.y = b.y - a.y;
30     d.z = b.z - a.z;
31     e.x = c.x - a.x;
32     e.y = c.y - a.y;
33     e.z = c.z - a.z;
34 
35     if (len1 == len2 && isVertical(d, e) && len1 != 0)
36     {
37         p.x = b.x + c.x - a.x;
38         p.y = b.y + c.y - a.y;
39         p.z = b.z + c.z - a.z;
40         return true;
41     }
42 
43     return false;
44 }
45 
46 bool isEqual(node a, node b) // 判断两个点是否相等
47 {
48     if (a.x == b.x && a.y == b.y && a.z == b.z) return true;
49     return false;
50 }
51 
52 int main()
53 {
54     int nCase;
55     scanf("%d", &nCase);
56     for (int cnt = 1; cnt <= nCase; ++cnt)
57     {
58         scanf("%I64d %I64d %I64d", &points[0].x, &points[0].y, &points[0].z);
59         scanf("%I64d %I64d %I64d", &points[1].x, &points[1].y, &points[1].z);
60         scanf("%I64d %I64d %I64d", &points[2].x, &points[2].y, &points[2].z);
61         scanf("%I64d %I64d %I64d", &points[3].x, &points[3].y, &points[3].z);
62 
63         printf("Case #%d: ", cnt);
64 
65         node p;
66         if (isSquare(points[0], points[1], points[2], p))
67         {
68             if (isEqual(p, points[3])) puts("Yes");
69             else puts("No");
70         }
71 
72         else if (isSquare(points[0], points[1], points[3], p))
73         {
74             if (isEqual(p, points[2])) puts("Yes");
75             else puts("No");
76         }
77 
78         else if (isSquare(points[0], points[2], points[3], p))
79         {
80             if (isEqual(p, points[1])) puts("Yes");
81             else puts("No");
82         }
83 
84         else puts("No");
85 
86     }
87     return 0;
88 }

1002 Greatest Greatest Common Divisor

题意：给定一组数，取两个数，使得

思路：用nVisit数组来记录每个数出现的次数，nCount数组来记录每个因子出现的次数。

枚举1—nMax内所有的因子，对任意一个因子i，存在j = k*i，nVisit[j]不为0，那么因子i存在。

我们从后往前找，当首次遇到nCount的值大于等于2的，就是答案。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 100005;
 6 int nVisit[MAXN];    // 记录数出现的次数
 7 int nCount[MAXN];   // nCount[i] = x 表示i这个因子出现了x次
 8 int nMax;            // 记录数组中最大的数
 9 void solve()
10 {
11     for (int i = 1; i <= nMax; ++i)
12     {
13         for (int j = i; j <= nMax; j += i)
14         {
15             // 判断是否有j这个数
16             if (nVisit[j])
17             {
18                 // 此时肯定有i这个因子,并求出几个数有i这个因子
19                 nCount[i] += nVisit[j];
20             }
21         }
22     }
23 }
24 
25 int main()
26 {
27     int nCase;
28     scanf("%d", &nCase);
29     for (int cnt = 1; cnt <= nCase; ++cnt)
30     {
31         int n;
32         scanf("%d", &n);
33 
34         nMax = 0;
35         memset(nVisit, 0, sizeof(nVisit));
36         memset(nCount, 0, sizeof(nCount));
37 
38         for (int i = 0; i < n; ++i)
39         {
40             int t;
41             scanf("%d", &t);
42             ++nVisit[t];
43             nMax = max(nMax, t);
44         }
45         solve();
46         printf("Case #%d: ", cnt);
47         for (int i = nMax; i >= 1; --i)
48         {
49             if (nCount[i] >= 2)
50             {
51                 printf("%d
", i);
52                 break;
53             }
54         }
55     }
56     return 0;
57 }