首页 > 代码库 > hdu 5839

hdu 5839

找立体四边形,至少4边相等;如果4边相等,不相等的两边必须相对。

比赛中一直没想通怎么统计正四面体,看题结,竟然是暴力。。。想想就能出数据hack了,不过,谁让数据水呢。。。

#include <cstdio>#include <cstring>#include <vector>#include <cmath>#include <stack>#include <cstdlib>#include <queue>#include <map>#include <iostream>#include <algorithm>#include <bits/stdc++.h>using namespace std;int cas=1;struct Point3{    int x,y,z;}a[210];int onepanel(Point3 a1,Point3 a2,Point3 a3,Point3 a4){    int A = ((a2.y-a1.y)*(a3.z-a1.z)-(a2.z-a1.z)*(a3.y-a1.y));    int B = ((a2.z-a1.z)*(a3.x-a1.x)-(a2.x-a1.x)*(a3.z-a1.z));    int C = ((a2.x-a1.x)*(a3.y-a1.y)-(a2.y-a1.y)*(a3.x-a1.x));    int D = -(A * a1.x + B * a1.y + C * a1.z);    int ret = A*a4.x+B*a4.y+a4.z*C+D;    if (ret==0) return 1;    else return 0;}int dis(Point3 a,Point3 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);}map<int,int>mp;map<int,int>::iterator it;int main(){    int T;    scanf ("%d",&T);    while (T--)    {        int n;        scanf ("%d",&n);        for (int i=0;i<n;i++)        {            scanf ("%d%d%d",&a[i].x,&a[i].y,&a[i].z);        }        int ans=0,zheng=0;        for (int i=0;i<n;i++)        {            for (int j=i+1;j<n;j++)            {                mp.clear();                int thi=dis(a[i],a[j]);                for (int k=0;k<n;k++)                {                    if (k!=i&&k!=j)                    {                        int ta=dis(a[i],a[k]),tb=dis(a[j],a[k]);                        if (ta==tb)                        {                            if (mp.find(ta)==mp.end())                                mp[ta]=0;                            mp[ta]++;                        }                    }                }                for (it=mp.begin();it!=mp.end();++it)                {                    if (it->second>=2)                    {                        ans+=(it->second)*(it->second-1)/2;                    }                }            }        }        printf ("%d\n",ans);        ans/=2;        int ccc=0;        for (int i=0;i<n;i++)        {            for (int j=i+1;j<n;j++)            {                for (int k=0;k<n;k++)                {                    if (k!=i&&k!=j&&dis(a[i],a[j])==dis(a[i],a[k])&&dis(a[i],a[j])==dis(a[k],a[j]))                    {                        for (int l=0;l<n;l++)                        {                            if (k!=l&&dis(a[i],a[j])==dis(a[i],a[l])&&dis(a[i],a[j])==dis(a[j],a[l])&&dis(a[i],a[j])==dis(a[k],a[l]))                                ccc++;                        }                    }                }            }        }        printf ("%d\n",ccc);        printf ("Case #%d: %d\n",cas++,ans-ccc/6);    }    return 0;}

 

hdu 5839