#include <bits/stdc++.h>
using namespace std;
struct Point
{
double x , y;
}p[85];
int n , cnt;
double x[85] , a1[85] , b1[85] , a2[85] , b2[85] , f[85][85];
bool check(Point p1 , Point p2)
{
double k = (p2.y - p1.y) / (p2.x - p1.x) , b = p2.y - k * p2.x;
for (int i = 1 ; i <= n ; i++)
{
if (x[i] > p2.x) continue;
double y = k * x[i] + b;
if (!((a1[i] <= y && y <= b1[i]) || (a2[i] <= y && y <= b2[i]))) return false;
}
return true;
}
int main()
{
cin >> n;
p[++cnt] = {0 , 5}; p[++cnt] = {10 , 5};
for (int i = 1 ; i <= n ; i++)
{
cin >> x[i] >> a1[i] >> b1[i] >> a2[i] >> b2[i];
p[++cnt] = {x[i] , a1[i]}; p[++cnt] = {x[i] , b1[i]}; p[++cnt] = {x[i] , a2[i]}; p[++cnt] = {x[i] , b2[i]};
}
for (int i = 1 ; i <= cnt ; i++)
{
for (int j = 1 ; j <= cnt ; j++)
{
if (check(p[i] , p[j])) f[i][j] = f[j][i] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
else f[i][j] = (i == j ? 0 : 1000);
//cout << f[i][j] << ' ';
}
// cout << endl;
}
for (int i = 1 ; i <= cnt ; i++)
for (int j = 1 ; j <= cnt ; j++)
for (int k = 1 ; k <= cnt ; k++)
f[j][k] = min(f[j][k] , f[j][i] + f[i][k]);
cout << fixed << setprecision(2) << f[1][2];
return 0;
}
样例,#1通过,其他推测全输出 1000(INF)。