首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2018 Wannafly summer camp Day2--New Game!

2018 Wannafly summer camp Day2--New Game!

作者头像
Enterprise_
发布2019-02-20 10:42:33
3090
发布2019-02-20 10:42:33
举报
文章被收录于专栏:小L的魔法馆小L的魔法馆

New Game! 描述 题目描述: Eagle Jump公司正在开发一款新的游戏。泷本一二三作为其员工,获得了提前试玩的机会。现在她正在试图通过一个迷宫。

这个迷宫有一些特点。为了方便描述,我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线L1:Ax+By+C1=0,L2:Ax+By+C2=0L1:Ax+By+C1=0,L2:Ax+By+C2=0 L_1:Ax+By+C_1=0, L_2:Ax+By+C_2=0,还有 n个圆Ci:(x−xi)2+(y−yi)2=ri2n个圆Ci:(x−xi)2+(y−yi)2=ri2n 个圆 C_i:(x-x_i)^2+(y-y_i)^2={r_i}^2。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。

泷本一二三想从L1L1 L_1​ 出发,走到 L2L2L_2​ 。请计算最少需要多少体力。

输入: 第一行五个正整数 n,A,B,C1,C2​(1≤n≤1000,−10000≤A,B,C1,C2≤10000)n,A,B,C1,C2​(1≤n≤1000,−10000≤A,B,C1,C2≤10000)n,A,B,C_1,C_2​ (1\le n \le 1000, -10000 \le A,B,C_1,C_2 \le 10000),其中 A,B 不同时为 0。

接下来 n 行每行三个整数 x,y,r(−10000≤x,y≤10000,1≤r≤10000)x,y,r(−10000≤x,y≤10000,1≤r≤10000)x,y,r(-10000 \le x,y \le 10000, 1\le r \le 10000)表示一个圆心为 (x,y),半径为 r 的圆。

输出: 仅一行一个实数表示答案。与标准答案的绝对误差或者相对误差不超过10−410−4 10^{-4} 即算正确。

样例输入 2 0 1 0 -4 0 1 1 1 3 1 样例输出 0.236068

由于圆是没有消耗的,所以可以将每个圆都坍缩成点,然后求L1到L2的最短路即可。

#include<iostream>
#include<cmath>
#include<cstdio>
#define MAXN 1005
using namespace std;
struct point
{
    double x, y;
    point() {

    }
};
struct line
{
    point a, b;
    line() {

    }
};

double distance(point p1, point p2)
{
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
double disptoline(point p1, double a, double b, double c)
{
    double x = sqrt(a*a + b*b);
    return fabs((a*p1.x + b*p1.y + c) / x);
}

point pp[1005];
double r[1005];
double e[1005][1005], d[1005];
int used[1005];
double inf = 1e9;
void dij(int s, int n)
{
    int v, u, max = 0;

    for (u = 0; u <= n; u++)
        d[u] = inf, used[u] = 0;

    d[s] = 0;


    while (1)
    {
        v = -1;
        for (u = 0; u <= n; u++)
        {
            if (!used[u] && (v == -1 || d[u]<d[v]))
                v = u;

        }
        if (v == -1) break;
        used[v] = 1;

        for (u = 0; u <= n; u++)
            if (d[u]>d[v] + e[v][u])
                d[u] = d[v] + e[v][u];
    }
}

int main()
{
    int n;
    double a, b, c1, c2;
    scanf("%d", &n);
    scanf("%lf%lf%lf%lf", &a, &b, &c1, &c2);
    for (int i = 0; i <= n + 1; i++)
    {
        for (int j = 0; j <= n + 1; j++)
            e[i][j] = inf;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf%lf", &pp[i].x, &pp[i].y, &r[i]);
    }

    for (int i = 1; i <= n; i++)
    {
        double lt = disptoline(pp[i], a, b, c1);

        if (lt<r[i]) e[0][i] = 0;
        else e[0][i] = lt - r[i];
    }
    for (int i = 1; i <= n; i++)
    {
        double lt = disptoline(pp[i], a, b, c2);
        if (lt<r[i]) e[i][n + 1] = 0;
        else e[i][n + 1] = lt - r[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            double lt = distance(pp[i], pp[j]);
            if (lt>r[i] + r[j]) e[i][j] = lt - r[i] - r[j];
            else e[i][j] = 0;
        }
    point t;
    t.y = 1.0, t.x = -(b*1.0 + c1) / a;
    e[0][n + 1] = disptoline(t, a, b, c2);
    dij(0, n + 1);

    printf("%.6f\n", d[n + 1]);
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年08月11日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档