code :
#include <cstdio> #include <cmath> #include <vector> #include <cstring> using namespace std; typedef double ld; const ld eps = 1e-13; int n; ld dis[75][75], ans[75]; ld x, d, md, mu, u; bool vis[75]; struct Point { ld x, y; Point(ld _x, ld _y) : x(_x), y(_y) {}; Point operator - (const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); } ld lenth() { return sqrt(x * x + y * y); } ld operator * (const Point &rhs) { return x * rhs.y - y * rhs.x; } friend ld len(Point &a, Point &b) { return (a - b).lenth(); } }; struct Line { Point s, e; Line(Point _s, Point _e) : s(_s), e(_e) {}; }; vector<Point> vec; vector<Line> vLine; int ok(ld a) { if (a > eps) return 1; return fabs(a) < eps ? 0 : -1; } bool check(Line a, Line b) { ld l = (a.s - b.s) * (a.e - b.s), r = (a.s - b.e) * (a.e - b.e); ld u = (b.s - a.s) * (b.e - a.s), d = (b.s - a.e) * (b.e - a.e); return ok(l) * ok(r) >= 0 || ok(u) * ok(d) >= 0; } void solve() { for (int i = 0; i < vec.size(); ++i) { for (int j = i + 1; j < vec.size(); ++j) { if (fabs(vec[i].x - vec[j].x) < eps) continue; dis[i][j] = 51; bool f = 1; for (int k = 0; k < vLine.size(); ++k) { if (!check(Line(vec[i], vec[j]), vLine[k])) { f = 0; break; } } if (f) dis[i][j] = len(vec[i], vec[j]); } } //printf("mid\n"); memset(vis, 0, sizeof vis); for (int i = 1; i < vec.size(); ++i)ans[i] = dis[0][i]; //vis[0] = 1; ans[0] = 0; for (int i = 0; i < vec.size(); ++i) { //printf("s\n"); int u; ld mn = 51; for (int j = 0; j < vec.size(); ++j) { if (!vis[j] && ans[j] < mn) { mn = ans[j]; u = j; } } vis[u] = 1; for (int j = 0; j < vec.size(); ++j) { if (!vis[j] && (ans[u] + dis[u][j] < ans[j])) { ans[j] = ans[u] + dis[u][j]; } } } printf("%.2lf\n", ans[vec.size() - 1]); } int main() { while (~scanf("%d", &n), ~n) { vec.clear(); vLine.clear(); vec.push_back(Point(0, 5)); //printf("1\n"); for (int i = 1; i < 4 * n + 1; i += 4) { scanf("%lf%lf%lf%lf%lf", &x, &d, &md, &mu, &u); //printf("%lf %lf\n", x, d); vec.push_back(Point(x, d)); vec.push_back(Point(x, md)); vec.push_back(Point(x, mu)); vec.push_back(Point(x, u)); dis[i][i + 1] = dis[i + 1][i] = md - d; dis[i][i + 2] = dis[i + 2][i] = dis[i][i + 3] = dis[i + 3][i] = 50; dis[i + 1][i + 2] = dis[i + 1][i + 3] = dis[i + 2][i + 1] = dis[i + 3][i + 1] = 50; dis[i + 2][i + 3] = dis[i + 3][i + 2] = u - mu; vLine.push_back(Line(Point(x, 0), Point(x, d))); vLine.push_back(Line(Point(x, md), Point(x, mu))); vLine.push_back(Line(Point(x, u), Point(x, 10))); } vec.push_back(Point(10, 5)); //printf("111\n"); solve(); } return 0; }