20分球跳(玄关*1)
查看原帖
20分球跳(玄关*1)
923403
FallingFYC_楼主2023/12/15 07:37
#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通过,其他推测全输出 10001000(INF)。

2023/12/15 07:37
加载中...