HDU 3400 Line belt

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 struct Point
 6 {
 7     double x,y;
 8 };
 9 
10 const double EPS=1e-10;
11 
12 double Dis(Point& a,Point& b)
13 {
14     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
15 }
16 int main()
17 {
18     int T;
19     scanf("%d",&T);
20     while(T--)
21     {
22         Point a,b,c,d;
23         scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
24         scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
25         int P,Q,R;
26         scanf("%d%d%d",&P,&Q,&R);
27 
28         Point left1=a,right1=b;
29         double ans=0;
30         do
31         {
32             Point mid1,midmid1;
33             double time1,time2;
34             mid1.x=(left1.x+right1.x)/2;
35             mid1.y=(left1.y+right1.y)/2;
36             time1=Dis(mid1,a)/P;
37             Point left2=c,right2=d;
38             do
39             {
40                 Point mid2,midmid2;
41                 mid2.x=(left2.x+right2.x)/2;
42                 mid2.y=(left2.y+right2.y)/2;
43                 double time21=Dis(mid1,mid2)/R;
44                 time21+=Dis(mid2,d)/Q;
45 
46                 midmid2.x=(mid2.x+right2.x)/2;
47                 midmid2.y=(mid2.y+right2.y)/2;
48                 double time22=(Dis(mid1,midmid2))/R;
49                 time22+=Dis(midmid2,d)/Q;
50                 if(time21<time22)
51                     right2=midmid2;
52                 else
53                     left2=mid2;
54             }while(Dis(left2,right2)>EPS);
55             time1+=Dis(mid1,left2)/R;
56             time1+=Dis(left2,d)/Q;
57 
58             midmid1.x=(mid1.x+right1.x)/2;
59             midmid1.y=(mid1.y+right1.y)/2;
60             time2=Dis(midmid1,a)/P;
61             left2=c;right2=d;
62             do
63             {
64                 Point mid2,midmid2;
65                 mid2.x=(left2.x+right2.x)/2;
66                 mid2.y=(left2.y+right2.y)/2;
67                 double time21=Dis(mid2,midmid1)/R;
68                 time21+=Dis(mid2,d)/Q;
69                 
70                 midmid2.x=(mid2.x+right2.x)/2;
71                 midmid2.y=(mid2.y+right2.y)/2;
72                 double time22=Dis(midmid1,midmid2)/R;
73                 time22+=Dis(midmid2,d)/Q;
74                 if(time21<time22)
75                     right2=midmid2;
76                 else
77                     left2=mid2;
78             }while(Dis(left2,right2)>EPS);
79             time2+=Dis(midmid1,left2)/R;
80             time2+=Dis(left2,d)/Q;
81             if(time1<time2)
82             {
83                 ans=time1;
84                 right1=midmid1;
85             }
86             else
87             {
88                 ans=time2;
89                 left1=mid1;
90             }
91         }while(Dis(left1,right1)>EPS);
92         printf("%.2lf\n",ans);
93     }
94     return 0;
95 }

posted on 2010-08-29 11:07 ZAKIR 阅读(225) 评论(0)  编辑 收藏 引用 所属分类: HDU


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜