| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:A了,精度问题导致ans<0WA了几次In Reply To:A了,精度问题导致ans<0WA了几次 Posted by:JiaJunpeng at 2011-05-10 21:13:39 附代码:
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
double x[4],y[4],z[4],xp,yp,zp,d,A,B,C,D,E,F,ans;
double ru1,ru2,eps=1e-4;
int main()
{
int i,j,s,p,q;
while(scanf("%lf%lf%lf",&x[0],&y[0],&z[0])==3)
{
ans=(double)1000000000*(double)1000000000;
for(i=1;i<4;i++)
scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
scanf("%lf%lf%lf%lf",&xp,&yp,&zp,&d);
A=(x[1]-x[0])*(x[1]-x[0])+(y[1]-y[0])*(y[1]-y[0])+(z[1]-z[0])*(z[1]-z[0]);
B=(x[3]-x[2])*(x[3]-x[2])+(y[3]-y[2])*(y[3]-y[2])+(z[3]-z[2])*(z[3]-z[2]);
C=2*(x[1]-x[0])*(x[2]-x[3])+2*(y[1]-y[0])*(y[2]-y[3])+2*(z[1]-z[0])*(z[2]-z[3]);
D=2*(x[0]-x[2])*(x[1]-x[0])+2*(y[0]-y[2])*(y[1]-y[0])+2*(z[0]-z[2])*(z[1]-z[0]);
E=2*(x[0]-x[2])*(x[2]-x[3])+2*(y[0]-y[2])*(y[2]-y[3])+2*(z[0]-z[2])*(z[2]-z[3]);
F=(x[0]-x[2])*(x[0]-x[2])+(y[0]-y[2])*(y[0]-y[2])+(z[0]-z[2])*(z[0]-z[2]);
double dist=(x[0]-xp)*(x[0]-xp)+(y[0]-yp)*(y[0]-yp)+(z[0]-zp)*(z[0]-zp);
if(dist<=d*d)
{
if(ans>F)
ans=F;
if(ans>B+E+F)
ans=B+E+F;
if(B!=0&&-E/(2*B)<=1&&-E/(2*B)>=0)
{
if(ans>F-E*E/(4*B))
ans=F-E*E/(4*B);
}
}
dist=(x[1]-xp)*(x[1]-xp)+(y[1]-yp)*(y[1]-yp)+(z[1]-zp)*(z[1]-zp);
if(dist<=d*d)
{
if(ans>A+D+F)
ans=A+D+F;
if(ans>A+B+C+D+E+F)
ans=A+B+C+D+E+F;
if(B!=0&&-(E+C)/(2*B)>=0&&-(E+C)/(2*B)<=1)
{
if(ans>A+D+F-(E+C)*(E+C)/(4*B))
ans=A+D+F-(E+C)*(E+C)/(4*B);
}
}
double aa,bb,cc;
aa=(x[1]-x[0])*(x[1]-x[0])+(y[1]-y[0])*(y[1]-y[0])+(z[1]-z[0])*(z[1]-z[0]);
bb=2*(x[1]-x[0])*(x[0]-xp)+2*(y[1]-y[0])*(y[0]-yp)+2*(z[1]-z[0])*(z[0]-zp);
cc=(x[0]-xp)*(x[0]-xp)+(y[0]-yp)*(y[0]-yp)+(z[0]-zp)*(z[0]-zp)-d*d;
for(i=0;i<2;i++)
{
if(i==0)
ru1=(-bb+sqrt(bb*bb-4*aa*cc))/(2*aa);
else
ru1=(-bb-sqrt(bb*bb-4*aa*cc))/(2*aa);
if(ru1>=0.00&&ru1<=1.00)
{
if(ans>A*ru1*ru1+D*ru1+F)
ans=A*ru1*ru1+D*ru1+F;
if(ans>B+C*ru1+E+A*ru1*ru1+D*ru1+F)
ans=B+C*ru1+E+A*ru1*ru1+D*ru1+F;
ru2=-(C*ru1+E)/(2*B);
if(ru2>=0&&ru2<=1)
{
if(ans>B*ru2*ru2+(C*ru1+E)*ru2+A*ru1*ru1+D*ru1+F)
ans=B*ru2*ru2+(C*ru1+E)*ru2+A*ru1*ru1+D*ru1+F;
}
}
}
ru1=-D/(2*A);
if(ru1<=1&&ru1>=0)
{
dist=(x[0]+ru1*(x[1]-x[0])-xp)*(x[0]+ru1*(x[1]-x[0])-xp);
dist+=(y[0]+ru1*(y[1]-y[0])-yp)*(y[0]+ru1*(y[1]-y[0])-yp);
dist+=(z[0]+ru1*(z[1]-z[0])-zp)*(z[0]+ru1*(z[1]-z[0])-zp);
if(dist<=d*d)
{
if(ans>A*ru1*ru1+D*ru1+F)
ans=A*ru1*ru1+D*ru1+F;
}
}
ru1=-(C+D)/(2*A);
if(ru1<=1&&ru1>=0)
{
dist=(x[0]+ru1*(x[1]-x[0])-xp)*(x[0]+ru1*(x[1]-x[0])-xp);
dist+=(y[0]+ru1*(y[1]-y[0])-yp)*(y[0]+ru1*(y[1]-y[0])-yp);
dist+=(z[0]+ru1*(z[1]-z[0])-zp)*(z[0]+ru1*(z[1]-z[0])-zp);
if(dist<=d*d)
{
if(ans>A*ru1*ru1+(C+D)*ru1+B+E+F)
ans=A*ru1*ru1+(C+D)*ru1+B+E+F;
}
}
if(4*A*B-C*C!=0)
{
ru1=(E*C-2*B*D)/(4*A*B-C*C);
ru2=(2*A*E-C*D)/(C*C-4*A*B);
if(ru1<=1&&ru1>=0&&ru2<=1&&ru2>=0)
{
dist=(x[0]+ru1*(x[1]-x[0])-xp)*(x[0]+ru1*(x[1]-x[0])-xp);
dist+=(y[0]+ru1*(y[1]-y[0])-yp)*(y[0]+ru1*(y[1]-y[0])-yp);
dist+=(z[0]+ru1*(z[1]-z[0])-zp)*(z[0]+ru1*(z[1]-z[0])-zp);
if(dist<=d*d)
{
if(ans>A*ru1*ru1+B*ru2*ru2+C*ru1*ru2+D*ru1+E*ru2+F)
ans=A*ru1*ru1+B*ru2*ru2+C*ru1*ru2+D*ru1+E*ru2+F;
}
}
}
if(ans<0)
ans=0;
ans=sqrt(ans);
printf("%.3lf\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator