HDU_5839

题意

三维空间里有n个点，取4个出来组成立体的四面体，要求其中至少有4条边是等长的。

思路

  1. 200个点，有199！条边，遍历边是不可能的……
  2. 设四条边相等，那么可能不相等的两条边必定是对立的，且他们的中点连线垂直这两条边。
  3. 200个点，先选出两个来，组成边（A-B），200^2复杂度，根据中点，可以做一个垂直（A-B）的面C，
    再遍历200个点，选出在面C的点。这些点是有可能组成立体的四边形的。复杂度O（200^3）
  4. 在选出来的点中遍历所有组合情况，看看满不满足条件2。
  5. 注意输入时的重点情况
  6. 的出来的满足条件的四面体会被重复计数，分为六边相等K和非两条边相等的P，总数为K/6+p/2
  7. 注意中点相等的情况

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#define eps 1e-5
using namespace std;
typedef long long ll;
ll neq,eq,ans;
int n;
struct node
{
    double x,y,z;
}p[300];
bool cmp(node a,node b)
{
    if(fabs(a.x-b.x)<=eps)
    {
        if(fabs(a.y-b.y)<=eps)
            return a.z<b.z;
        return a.y<b.y;
    }
    return a.x<b.x;
}
void work(node a,node b){
    int getin[300],cnt=0;
    double dis1=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
    double dis2;
    node mid,mid2;
    mid.x=(a.x+b.x)/2,   mid.y=(a.y+b.y)/2,   mid.z=(a.z+b.z)/2;
    double k1,k2,k3,d;
    k1=a.x-b.x,k2=a.y-b.y,k3=a.z-b.z;
    d=k1*mid.x+k2*mid.y+k3*mid.z;
    for(int i=0;i<n;i++)
        if(fabs(k1*p[i].x+k2*p[i].y+k3*p[i].z-d)<=eps)
            getin[cnt++]=i;
    if(cnt<1)return ;
    double m1,m2,m3,l1,l2,l3;
    for(int i=0;i<cnt;i++)
    {
        double tx=p[getin[i]].x,ty=p[getin[i]].y,tz=p[getin[i]].z;
        for(int j=i+1;j<cnt;j++)
        {
            double t2x=p[getin[j]].x,t2y=p[getin[j]].y,t2z=p[getin[j]].z;
            mid2.x=(tx+t2x)/2;  mid2.y=(ty+t2y)/2;  mid2.z=(tz+t2z)/2;
            m1=mid2.x-mid.x;    m2=mid2.y-mid.y;    m3=mid2.z-mid.z;
            if(fabs(m1)<=eps && fabs(m2)<=eps && fabs(m3)<=eps)continue;
            double dis3 = (tx-a.x)*(tx-a.x)+(ty-a.y)*(ty-a.y)+(tz-a.z)*(tz-a.z);
            l1=tx-t2x;  l2=ty-t2y;  l3=tz-t2z;
            if(fabs( m1*l1 + m2*l2 + m3*l3)<=eps)
            {
                dis2 = l1*l1 + l2*l2 + l3*l3;
                if(fabs((dis1-dis2))<=eps && fabs(dis3-dis1)<=eps)eq++;
                else neq++;
            }
        }
    }
}
int main()
{
    int cas=0,T;
    scanf("%d",&T);
    while(T--)
    {
        ans=0,eq=0,neq=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
        sort(p,p+n,cmp);
        int nn=1;
        for(int i=1;i<n;i++)
        {
            if((fabs(p[i].x-p[i-1].x)<=eps)&&(fabs(p[i].y-p[i-1].y)<=eps)&&(fabs(p[i].z-p[i-1].z)<=eps))
                continue;
            else
            {
                p[nn].x=p[i].x;
                p[nn].y=p[i].y;
                p[nn].z=p[i].z;
                nn++;
            }
        }
        n=nn;
        if(n<4)
        {
            printf("Case #%d: 0\n",++cas);
            continue;
        }
        for(int i=0;i<n;i++)
           for(int j=i+1;j<n;j++)
                work(p[i],p[j]);
        ans=eq/6+neq/2;
        printf("Case #%d: %I64d\n",++cas,ans);
    }
    return 0;
}