题意: n个点中,选出4个点出来构成一个四面体,要求四面体至少有四条棱要相等。并且不想等的两条棱不能相邻。
思路:1. 据说N^4直接暴力加一点点的优化就可以过了。
2.我们可以枚举每条棱,假设它与其他棱不想等,那么我们再去枚举点,找到一群与该线段的两个端点的距离相等的点,那么我们再去找这群点中找出 与改线段的端点的距离相等的点对,现在这四个点组成的四面体就满足了第一个条件,再去判断下是否四点共面即可。我们可以注意到:如果只有四条棱相等,那么,我们每个四面体枚举了两次(两条对边,一条枚举了一次),如果是有五条棱相等,同四条棱一样,枚举了两次。但是如果是六条棱都相等时,那么同一个四面体枚举了六次。
代码如下:
#include<stdio.h> #include<string.h> #include<math.h> #include<queue> #include<vector> #include<iostream> #include<complex> #include<string> #include<set> #include<map> #include<algorithm> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define nn 330 #define ll long long #define ULL unsiged long long #define mod 0x7fffffff #define inf oxfffffffffff #define eps 0.000000001 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 struct point { ll x, y,z; ll len; point(ll x = 0, ll y = 0,ll z=0) :x(x), y(y),z(z) {} }; point operator + (point A, point B) { return point(A.x + B.x, A.y + B.y, A.z + B.z); } point operator - (point A, point B) { return point(A.x - B.x, A.y - B.y, A.z - B.z); } point operator * (point A, ll p) { return point(A.x*p, A.y*p, A.z*p); } point operator * (point A, point B)//叉乘 { point pos; pos.x = A.y*B.z - A.z*B.y; pos.y = A.z*B.x - A.x*B.z; pos.z = A.x*B.y - A.y*B.x; return pos; } point operator / (point A, ll p) { return point(A.x / p, A.y / p, A.z / p); } int dcmp(ll x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } bool operator == (const point A, const point B) { return dcmp(A.x - B.x) && dcmp(A.y - B.y) && dcmp(A.z - B.z); } ll dot(point A, point B)//点乘 { return A.x*B.x + A.y*B.y + A.z*B.z; } ll length(point A)//就算距离的平方 { return dot(A,A); } bool cmp(point A, point B) { return A.len < B.len; } bool is_ok(point A, point B, point C, point D)//判断是否四点共面 { point x = (A - B)*(B - C); return dot(x, D - A) == 0LL; } point p[nn], v[nn]; int main() { int n, kcae = 1,t; scanf("%d", &t); while (t--) { int ans = 0, ans6 = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].z); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int cnt = 0; ll len = length(p[i] - p[j]); for (int k = 0; k < n; k++) { ll len1 = length(p[i] - p[k]); ll len2 = length(p[j] - p[k]); if (len1 == len2) { v[cnt] = p[k]; v[cnt++].len = len1; } } for (int k = 0; k < cnt; k++) { for (int kk = k+1; kk < cnt; kk++) { if (v[k].len != v[kk].len) continue; if (is_ok(p[i], p[j],v[k], v[kk])) continue; ans++; ll tmp = length(v[k] - v[kk]); if (tmp == len && len != v[k].len) ans--; if (len == v[k].len && len == tmp) ans6++; } } } } ans /= 2; ans -= ans6 / 3; printf("Case #%d: %d\n", kcae++, ans); } return 0; } WA了一万发,发现输出答案的地方没加“#”,我也是*了*了。