首页 > 代码库 > 【HDOJ】3400 Line belt
【HDOJ】3400 Line belt
三分。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 5 typedef struct { 6 double x, y; 7 } Point_t; 8 9 Point_t A, B, C, D;10 const double eps = 1.0e-8;11 double P, Q, R;12 13 double dist(Point_t a, Point_t b) {14 return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));15 }16 17 double t_ab(Point_t a, Point_t b) {18 return dist(a, b)/P;19 }20 21 double t_cd(Point_t c, Point_t d) {22 return dist(c, d)/Q;23 }24 25 double t_oth(Point_t x, Point_t y) {26 return dist(x, y)/R;27 }28 29 double tri_cd(Point_t c, Point_t d, Point_t S) {30 Point_t left = c, right = d;31 Point_t p1, p2;32 33 while (dist(left, right) > eps) {34 p1.x = left.x*2.0/3.0 + right.x/3.0;35 p1.y = left.y*2.0/3.0 + right.y/3.0;36 p2.x = left.x/3.0 + right.x*2.0/3.0;37 p2.y = left.y/3.0 + right.y*2.0/3.0;38 if (t_oth(S, p1)+t_cd(p1, D) <= t_oth(S, p2)+t_cd(p2, D)) {39 right = p2;40 } else {41 left = p1;42 }43 }44 return t_oth(S, left) + t_cd(left, d);45 }46 47 double tri_ab(Point_t a, Point_t b) {48 Point_t left = a, right = b;49 Point_t p1, p2;50 51 while (dist(left, right) > eps) {52 p1.x = left.x*2.0/3.0 + right.x/3.0;53 p1.y = left.y*2.0/3.0 + right.y/3.0;54 p2.x = left.x/3.0 + right.x*2.0/3.0;55 p2.y = left.y/3.0 + right.y*2.0/3.0;56 if (t_ab(a, p1)+tri_cd(C, D, p1) <= t_ab(a, p2)+tri_cd(C, D, p2)) {57 right = p2;58 } else {59 left = p1;60 }61 }62 return t_ab(a, left) + tri_cd(C, D, left);63 }64 65 int main() {66 int t;67 68 scanf("%d", &t);69 while (t--) {70 scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);71 scanf("%lf%lf%lf%lf",&C.x,&C.y,&D.x,&D.y);72 scanf("%lf%lf%lf", &P, &Q, &R);73 printf("%.2lf\n", tri_ab(A, B));74 }75 76 return 0;77 }
【HDOJ】3400 Line belt
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。