題目：Line belt

?

題意：就是給你兩條線段AB , CD ，一個人在AB上跑速度p, 在CD上跑q,在其他地方跑速度是r。問你從A到D最少的時間是好多。

#include<iostream> #include<cmath> #include <stdio.h> using namespace std;typedef struct {double x , y ; }point;point a,b,c,d; int p , q , r ; const double eps = 1e-8;double dis( point p1 , point p2 ) {double l = (p2.x-p1.x ) * ( p2.x - p1.x ) + (p2.y-p1.y) * (p2.y - p1.y );return sqrt(l) ; }double part(double k) {double Lx = 0 , Rx = dis(c, d);point e , f1 ,f2;for(int i = 0 ; i < 200 ;++i){double len = Rx - Lx ;double t1 = Lx + len * 4/9;double t2 = Lx + len *5/9;e.x = a.x + k * (b.x - a.x );e.y = a.y + k * ( b.y -a.y );f1.x = c.x + (t1 * (d.x - c.x ));f1.y = c.y + (t1* (d.y - c.y ));f2.x = c.x + (t2 * (d.x - c.x ));f2.y = c.y + (t2 * (d.y - c.y ));double res1 = dis(a,e)/p + dis(e,f1)/r + dis(f1,d)/q;double res2 = dis(a,e)/p + dis(e,f2)/r + dis(f2,d)/q;if( res1 < res2) Rx = t2 ;else Lx = t1 ;}double t = (Lx+Rx)/2.0;e.x = a.x + (k * (b.x - a.x )) ;e.y = a.y + (k * ( b.y -a.y )) ;f1.x = c.x + (t * (d.x - c.x ));f1.y = c.y + (t* (d.y - c.y));return dis(a,e)/p + dis(e,f1)/r + dis(f1,d)/q; }double solve(double Min , double Max ) {double Lx = Min , Rx = Max ;for(int i = 0 ; i < 200 ; ++i){double len = Rx - Lx ;double t1 = Lx + len * 4/9 ;double t2 = Lx + len* 5/9 ;double f1 = part(t1);double f2 = part(t2);if( f1 < f2) Rx = t2 ;else Lx = t1;}return part((Lx+Rx)/2.0); } int main() {int t ;scanf("%d",&t);while(t--){scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);scanf("%d%d%d",&p,&q,&r);double res = solve(0.0, 1.0);printf("%.2f\n",res);}return 0 ; }

?

?

總結

以上是生活随笔為你收集整理的HDU3400(计算几何中的三分法利用)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。