POJ - 2031 Building a Space Station(几何+prim)

题目链接:

  https://vjudge.ppsucxtt.cn/problem/POJ-2031

思路:

   又是prim模板题,只要知道立体几何中:两球之间的距离等于两球的圆心距离减去两求半径,当两球之间的距离小于等于两球的圆心距离减去两球半径则两球相交距离为0,再就是处理数据+prim()。

代码:

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 110;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 998244353;

struct node
{
    double x, y, z, r;
};

int n, m;
double a[N][N];
node data[N];
bool vis[N];
double dis[N];

double prim()
{
    memset(vis, 0, sizeof vis);
    for (int i = 0; i <= n; i++)
        dis[i] = 2e8;
    double res = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j])
                continue;
            if (t == -1 || dis[j] < dis[t])
                t = j;
        }
        vis[t] = 1;
        if (t != 1)
            res += dis[t];
        for (int j = 1; j <= n; j++)
            dis[j] = min(dis[j], a[t][j]);
    }
    return res;
}

int main()
{
    fastio;
    while (cin >> n)
    {
        if (n == 0)
            break;
        for (int i = 1; i <= n; i++)
            cin >> data[i].x >> data[i].y >> data[i].z >> data[i].r;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                double s = sqrt(pow(data[i].x - data[j].x, 2.0) + pow(data[i].y - data[j].y, 2.0) + pow(data[i].z - data[j].z, 2.0));
                if (s <= data[i].r + data[j].r)
                    a[i][j] = a[j][i] = 0;
                else
                    a[i][j] = a[j][i] = s - (data[i].r + data[j].r);
            }
        cout << fixed << setprecision(3) << prim() << endl;
    }

    return 0;
}

 

上一篇:新认识属性


下一篇:动态规划dp