Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:A了,精度问题导致ans<0WA了几次

Posted by Test_Rush at 2011-05-10 21:16:43 on Problem 2913
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator