首页 > 代码库 > UVA 10089 Repackaging 数学问题
UVA 10089 Repackaging 数学问题
大致题意：给出几个包裹，每个包裹都包装好了3种大小的杯子。现在要重新包装，使向量
a[1]*(s[1][1],s[1][2],s[1][3])+a[2]*(s[2][1],s[2][2],s[2][3])+.....+a[n]*(s[n][1],s[n][2],s[n][3])=(k,k,k). 就这样转化成了向量问题其中a[i]为非负整数，k为正整数。
虽然转化成了向量问题，但是三维向量和这么多变量有点棘手，所以我们可以先降维，将原等式变化成：
a[1]*(s[1][2]-s[1][1],s[1][3]-s[1][1])+ a[2]*(s[2][2]- s[2][1],s[2][3]- s[2][1])+.....+a[n]*(s[n][2]- s[n][1],s[n][3]- s[n][1])=(0,0).
把二维向量看成以平面坐标系中以原点为起点的向量。如果只有两个向量，因为a[i]为非负数，所以只有两个向量的时候夹角必须为PI。n个向量的话，只要相邻两个向量的夹角不大于PI即可满足上述等式。代码不长，但是需要数学思维T_T
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int maxn=1000+5;const double PI=acos(-1);int main(){ int n; double A[maxn]; while(scanf("%d",&n),n) { int s1,s2,s3; for(int i=0;i<n;i++) { scanf("%d%d%d",&s1,&s2,&s3); A[i]=atan2(s2-s1,s3-s1); } sort(A,A+n); double tmp=0; for(int i=1;i<n;i++) tmp=max(tmp,A[i]-A[i-1]); tmp=max(tmp,A[0]-A[n-1]+2*PI); if(tmp<=PI) printf("Yes\n"); else printf("No\n"); } return 0;}
UVA 10089 Repackaging 数学问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。