1001 Four Inages Strategy
题意：给定空间的四个点，判断这四个点是否能形成正方形
思路：判断空间上4个点是否形成一个正方形方法有很多，这里给出一种方法，在p2,p3,p4中枚举两个点作为p1的邻点，
不妨设为pi，pj，然后判断p1pi与p1pj是否相等、互相垂直，然后由向量法，最后一个点坐标应该为pi+pj−p1，判断是否相等就好了。
#include <cstdio>
using namespace std; struct node
{
__int64 x, y, z;
}; node points[]; // 存放四个点坐标 __int64 dist(node a, node b) // 计算两点之间的距离
{
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);
} bool isVertical(node a, node b) // 判断两个向量是否垂直
{
if (a.x * b.x + a.y * b.y + a.z * b.z == ) return true;
return false;
} bool isSquare(node a, node b, node c, node& p) // 判断是否为等腰直角（成正方形的必要条件）
{
__int64 len1 = dist(a, b);
__int64 len2 = dist(a, c); node d, e;
d.x = b.x - a.x;
d.y = b.y - a.y;
d.z = b.z - a.z;
e.x = c.x - a.x;
e.y = c.y - a.y;
e.z = c.z - a.z; if (len1 == len2 && isVertical(d, e) && len1 != )
{
p.x = b.x + c.x - a.x;
p.y = b.y + c.y - a.y;
p.z = b.z + c.z - a.z;
return true;
} return false;
} bool isEqual(node a, node b) // 判断两个点是否相等
{
if (a.x == b.x && a.y == b.y && a.z == b.z) return true;
return false;
} int main()
{
int nCase;
scanf("%d", &nCase);
for (int cnt = ; cnt <= nCase; ++cnt)
{
scanf("%I64d %I64d %I64d", &points[].x, &points[].y, &points[].z);
scanf("%I64d %I64d %I64d", &points[].x, &points[].y, &points[].z);
scanf("%I64d %I64d %I64d", &points[].x, &points[].y, &points[].z);
scanf("%I64d %I64d %I64d", &points[].x, &points[].y, &points[].z); printf("Case #%d: ", cnt); node p;
if (isSquare(points[], points[], points[], p))
{
if (isEqual(p, points[])) puts("Yes");
else puts("No");
} else if (isSquare(points[], points[], points[], p))
{
if (isEqual(p, points[])) puts("Yes");
else puts("No");
} else if (isSquare(points[], points[], points[], p))
{
if (isEqual(p, points[])) puts("Yes");
else puts("No");
} else puts("No"); }
return ;
}
1002 Greatest Greatest Common Divisor
题意：给定一组数，取两个数，使得gcd最大，求最大gcd值。
思路：用nVisit数组来记录每个数出现的次数，nCount数组来记录每个因子出现的次数。
枚举1—nMax内所有的因子，对任意一个因子i，存在j = k*i，nVisit[j]不为0，那么因子i存在。
我们从后往前找，当首次遇到nCount的值大于等于2的，就是答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = ;
int nVisit[MAXN]; // 记录数出现的次数
int nCount[MAXN]; // nCount[i] = x 表示i这个因子出现了x次
int nMax; // 记录数组中最大的数
void solve()
{
for (int i = ; i <= nMax; ++i)
{
for (int j = i; j <= nMax; j += i)
{
// 判断是否有j这个数
if (nVisit[j])
{
// 此时肯定有i这个因子,并求出几个数有i这个因子
nCount[i] += nVisit[j];
}
}
}
} int main()
{
int nCase;
scanf("%d", &nCase);
for (int cnt = ; cnt <= nCase; ++cnt)
{
int n;
scanf("%d", &n); nMax = ;
memset(nVisit, , sizeof(nVisit));
memset(nCount, , sizeof(nCount)); for (int i = ; i < n; ++i)
{
int t;
scanf("%d", &t);
++nVisit[t];
nMax = max(nMax, t);
}
solve();
printf("Case #%d: ", cnt);
for (int i = nMax; i >= ; --i)
{
if (nCount[i] >= )
{
printf("%d\n", i);
break;
}
}
}
return ;
}