专栏首页饶文津的专栏【HDU 5839】Special Tetrahedron(计算几何)

【HDU 5839】Special Tetrahedron(计算几何)

空间的200个点,求出至少四边相等,且其余两边必须不相邻的四面体的个数。

用map记录距离点i为d的点有几个,这样来优化暴力的四重循环。

别人的做法是枚举两点的中垂面上的点,再把到中点距离相等的点找出来,n^3的样子。

还要注意四个点共面的情况。

共面判断就是用叉乘计算出ijk三点所在面的法向量,然后判断il向量是否和法向量垂直,是则共面。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#define eps (1e-6)
#define N 205
#define dd double
#define sqr(x) ((x)*(x))
using namespace std;
map<double,int>mm[N];
int ok[N];
struct node{
    int x,y,z;
}a[N];
dd Dis[N][N];
dd dis(int i,int j)
{
    if(Dis[i][j])return Dis[i][j];
    return Dis[i][j]=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)+sqr(a[i].z-a[j].z));
}
node xmul(node i,node j,node k){
        int z=(i.x-j.x)*(k.y-j.y)-(i.y-j.y)*(k.x-j.x);
        int y=(i.z-j.z)*(k.x-j.x)-(i.x-j.x)*(k.z-j.z);
        int x=(i.y-j.y)*(k.z-j.z)-(i.z-j.z)*(k.y-j.y);
        return (node){x,y,z};
}
node xmul(int i,int j,int k){
    return xmul(a[i],a[j],a[k]);
}
int sgn(dd a,dd b){
    return fabs(a-b)>-eps&&fabs(a-b)<eps;
}
int te(int i,int j,int k,int l){//共面
    node il=(node){a[i].x-a[l].x,a[i].y-a[l].y,a[i].z-a[l].z};
    node s=xmul(i,j,k);
    return s.x*il.x+s.y*il.y+s.z*il.z;
}
int main() {
    int t,n;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        int ans=0,same=0;
        memset(ok,0,sizeof ok);
        memset(Dis,0,sizeof Dis);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)mm[i].clear();
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            mm[i][dis(i,j)]++;
            if(mm[i][dis(i,j)]>1){ok[i]=1;break;}
        }
        for(int i=1;i<=n;i++)if(ok[i])
        for(int j=i+1;j<=n;j++)if(ok[j])
        for(int k=i+1;k<=n;k++)if(ok[k]){
                dd ij=dis(i,j),ik=dis(i,k),jk=dis(j,k);
                if(sgn(jk,ik))
                    for(int l=k+1;l<=n;l++)if(l!=j){
                        dd jl=dis(j,l),lk=dis(l,k),il=dis(i,l);
                        if(te(i,j,k,l)){
                            if(sgn(jk,jl)&&sgn(jl,il)&&sgn(il,jl))
                            {
                                ans++;
                                if(sgn(ij,lk)&&sgn(ij,ik))same++;
                            }
                        }                    
                    }
        }
        printf("Case #%d: %d\n",cas,ans-same/3*2);//全部边相同的会计算3次
    }
}

赛后做出来的,为什么当时暴力都写不出来呢,因为在防止多算的时候给漏算了。枚举出错。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【POJ 1698】Alice's Chance(二分图多重匹配)

    饶文津
  • 【ZOJ2278】Fight for Food(dp)

    给定一个10*10以内的地图,和p(P<=30000)只老鼠,给定其出现位置和时间T(T<=1,000,000,000),求最多抓到几只老鼠。

    饶文津
  • 「AtCoder Grand018B」Sports Festival(暴力)

    饶文津
  • 1077: 输入入门(2)

    描述:计算A+B 输入:输入第1行为一个整数n(1≤n≤10),代表测试的组数。下面有n组测试数据,每组1行,为2个整数,为A, B。 输出:输出A+B的值...

    bboysoul
  • 【ZOJ2278】Fight for Food(dp)

    给定一个10*10以内的地图,和p(P<=30000)只老鼠,给定其出现位置和时间T(T<=1,000,000,000),求最多抓到几只老鼠。

    饶文津
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • 【POJ 1698】Alice's Chance(二分图多重匹配)

    饶文津
  • Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

    题意:有n个节目,每个节目有一个持续的天数,你一天只能看一个节目,问你这么多天最多能看几个节目

    ShenduCC
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券