空间的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=;cas<=t;cas++){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
int ans=,same=;
memset(ok,,sizeof ok);
memset(Dis,,sizeof Dis);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)mm[i].clear();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
mm[i][dis(i,j)]++;
if(mm[i][dis(i,j)]>){ok[i]=;break;}
}
for(int i=;i<=n;i++)if(ok[i])
for(int j=i+;j<=n;j++)if(ok[j])
for(int k=i+;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+;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次
}
}

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

最新文章

  1. kqueue例子
  2. gem安装报错解决方法
  3. 生成PHP数组文件
  4. docker debug diagnose
  5. Javascript位置 body之前、后执行顺序
  6. Spring配置MyBatis
  7. 02_线程的创建和启动_继承Thread方式
  8. Reorder the Books(规律)
  9. DDD领域驱动设计仓储Repository
  10. Yii Framework2.0开发教程(10)配合mysql数据库实现用户登录
  11. Kafka 0.8源码分析—ZookeeperConsumerConnector
  12. 如何使用MFC连接Access数据库
  13. 单因素方差分析的SAS实现
  14. vue学习一:新建或打开vue项目(vue-cli2)
  15. shell加密工具shc的安装和使用
  16. 关于Linux防火墙&#39;iptables&#39;的面试问答
  17. [HTML5]移动平台的HTML5开发框架
  18. trycatch之catch对捕获异常的处理及后续代码的执行的探索
  19. .NET 中使用 TaskCompletionSource 作为线程同步互斥或异步操作的事件
  20. HTTP监视器charles入门使用教程分享---http/s packet monitors---ubuntu installation

热门文章

  1. ajax asud模板
  2. Android入门篇2-activity调用跟数据传递
  3. Kubernetes deployed on multiple ubuntu nodes
  4. VMWare发布ESXi 6.0
  5. JavaScript的闭包和内存泄漏问题
  6. swift 随机生成背景颜色
  7. 转:如何在32位程序中突破地址空间4G的限制
  8. swift导航栏导航按钮添加多个按钮事件
  9. 翻译qmake文档(二) Getting Started
  10. C#读取网络流,读取网络上的js文件