首页 > 代码库 > hdu5017：补题系列之西安网络赛1011
hdu5017：补题系列之西安网络赛1011
补题系列之西安网络赛1011
题目大意：给定一个椭球： 
求它到原点的最短距离.
思路：
对于一个椭球的标准方程 x^2/a^2 + y^2/b^2 +z^2/c^2=1 来说，它到原点的最短距离即为min(a,b,c)
所以我们需要把原方程化为标准型。
这时候线代就排上用场了，注意到原方程是一个二次型。
化为标准型 1/(k1)*x^2+1/(k2)*y^2+1/(k3)*z^2=1 后 min(k1,k2,k3)即为答案
而这里的1/k1,1/k2,1/k3 就是二次型矩阵的特征值
如何求特征值呢？
我们写出二次型矩阵
| a f/2 e/2 |
T= | f/2 b d/2 |
| e/2 d/2 c | 由行列式| λE-T|=0 可以得到一个关于λ的一元三次方程,令 k=1/λ,
把它记为 a*k^3+b*k^2+c*k+d=0(注意这里的a,b,c,d都是关于原方程中a,b,c,d的多项式)
解这个一元三次方程，可以使用求根公式：盛金公式（其他方法我还不会）
分此四种情况讨论求解即可。。
代码：
#include <stdio.h>#include<algorithm>#include<math.h>using namespace std;#define MAXN 10000const double p=sqrt(3.0);const double inf=0.0000001;double min(double a,double b,double c){ return min(a,min(b,c));}int main(){ double aa,bb,cc,dd,ee,ff; double A,B,C,a,b,c,d; while(scanf("%lf%lf%lf%lf%lf%lf",&aa,&bb,&cc,&dd,&ee,&ff)!=EOF) { double ans; a=4*aa*bb*cc+dd*ee*ff-bb*ee*ee-aa*dd*dd-ff*ff*cc; b=4*aa*bb+4*bb*cc+4*aa*cc-ee*ee-ff*ff-dd*dd; c=4*aa+4*bb+4*cc; d=4.0; A=b*b-3*a*c; B=b*c-9*a*d; C=c*c-3*b*d; double q=B*B-4*A*C; if(fabs(A-B)<inf&&fabs(A)<inf) { printf("%.8lf\n",sqrt(fabs(-c/b))); continue; } if(fabs(B*B-4*A*C)<inf) { double k=B/A; ans=min(fabs(-b/a+k),fabs(-k/2)); printf("%.8f\n",sqrt(ans)); continue; } if(q>0) { double x=A*b+3*a*((-B+sqrt(q))/2); double y=A*b+3*a*((-B-sqrt(q))/2); double t1= x>0?pow(x,1.0/3):-(pow(fabs(x),1.0/3)); double t2= y>0?pow(y,1.0/3):-(pow(fabs(y),1.0/3)); ans=(-b-t1-t2)/(3*a); printf("%.8f\n",sqrt(fabs(ans))); continue; } double t=acos((2*A*b-3*a*B)/(2*sqrt(A*A*A)))/3; ans=min(fabs((-b-2*sqrt(A)*cos(t))/(3*a)),fabs(((-b)+sqrt(A)*(cos(t)+p*sin(t)))/(3*a)),fabs(((-b)+sqrt(A)*(cos(t)-p*sin(t)))/(3*a))); printf("%.8f\n",sqrt(ans)); } return 0;}
hdu5017：补题系列之西安网络赛1011
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。