CodeforcesRound#265(Div.2)D.RestoreCube立方体判断_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#265(Div.2)D.RestoreCube立方体判断_html/css_WEB-ITnose,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2480字,纯文字阅读大概需要4分钟。
内容图文
![CodeforcesRound#265(Div.2)D.RestoreCube立方体判断_html/css_WEB-ITnose](/upload/InfoBanner/zyjiaocheng/399/7c5ce6d8cdbc4f3e93f5673a98cbc563.jpg)
给定8个点坐标,对于每个点来说,可以随意交换x,y,z坐标的数值。问说8个点是否可以组成立方体。
暴力枚举即可,注意检查立方体姿势不对会T
如果8个点形成一个立方体是这样的:找到所有点对之间的最小距离,应等于边的长度L。每个顶点应该正好有三个点距离它为L,而且构成的三个边应两两垂直。如果这些条件都满足在每一点上,那么一定只能是立方体。检查复杂度约O(8^2)。
#include#include #include #include #include #include #include #include #include #include using namespace std;#define RD(x) scanf("%d",&x)#define RD2(x,y) scanf("%d%d",&x,&y)#define clr0(x) memset(x,0,sizeof(x))typedef long long LL;typedef pair<int, int> pii;const double eps = 1e-9;const double pi = acos(-1.0);LL dianji(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){ return x1*x2+y1*y2+z1*z2;}LL dist2(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){ return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);}LL v[8][3],minl[8],l;int cntmin[8],to[8][8];int index[8];bool chuizhi(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2){ return dianji(x1,y1,z1,x2,y2,z2) == 0;}bool chuizhi(int i,int a,int b){ return chuizhi(v[a][0] - v[i][0],v[a][1] - v[i][1],v[a][2] - v[i][2],v[b][0] - v[i][0],v[b][1] - v[i][1],v[b][2] - v[i][2]);}bool chuizhi(int i,int a,int b,int c){ return chuizhi(i,a,b)&&chuizhi(i,b,c)&&chuizhi(i,a,c);}bool check(){ clr0(index),clr0(minl),clr0(cntmin); for(int i = 0;i < 8;++i){ for(int j = i + 1;j < 8;++j){ l = dist2(v[i][0],v[i][1],v[i][2],v[j][0],v[j][1],v[j][2]); if(!minl[i] || minl[i] > l) minl[i] = l,to[i][cntmin[i] = 0] = j; else if(minl[i] == l) to[i][++cntmin[i]] = j; if(!minl[j] || minl[j] > l) minl[j] = l,to[j][cntmin[j] = 0] = j; else if(minl[j] == l) to[j][++cntmin[j]] = i; } if(cntmin[i]!=2 || !minl) return false; if(!chuizhi(i,to[i][0],to[i][1],to[i][2])) return false; } return true;}bool find(int x){ if(x == 8){ return check(); } do{ if(find(x+1)) return true; }while(next_permutation(v[x],v[x]+3)); return false;}int main() { for(int i = 0;i < 8;++i){ scanf("%I64d%I64d%I64d",&v[i][0],&v[i][1],&v[i][2]); sort(v[i],v[i]+3); } if(!find(0)) puts("NO"); else{ puts("YES"); for(int i = 0;i < 8;++i){ printf("%I64d %I64d %I64d\n",v[i][0],v[i][1],v[i][2]); } } return 0;}
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#265(Div.2)D.RestoreCube立方体判断_html/css_WEB-ITnose全部内容,希望文章能够帮你解决CodeforcesRound#265(Div.2)D.RestoreCube立方体判断_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。