穿越银河

[编程题]穿越银河

热度指数：259 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在浩瀚深邃的星空中，有若干个可以被视为质点的星球，以及坐着飞船想要探索宇宙奥秘的度度熊。

我们假定银河是一个 $n \times m$ 的区域，顶点在 $\text (0,0)$ 和 $(\mathit n,m)$ ，度度熊从最左边任意一点进入，打算穿越这片区域并从右边任意一点离开。

在银河中分布着 $\mathit k$ 个星球，每个星球以及银河的上下两个边缘都有引力，处于安全考虑，度度熊要离他们越远越好。
试求度度熊穿越银河的路径上，距离所有星球以及上下边界的最小距离的最大值可以为多少？

输入描述:

第一行包含三个整数 。
接下来行，每行两个整数表示一个点的坐标。

输出描述:

一个实数表示答案，保留4位小数。

示例1

输入

10 5 2
1 1
2 3

输出

1.1180

算法知识视频讲解

Tanix

#include <iostream>
#include <iomanip>
#include <sstream>
#include <array>
using namespace std;

const int KMAX = 6000, PRECISION = 4;
array<int, KMAX> x, y, parents;
array<bool, KMAX> cover_up, cover_down;  // 星球引力范围是否与边界引力范围相接
array<array<double, KMAX>, KMAX> distance_squares;

// 计算距离平方
double get_distance_square(int x1, int y1, int x2, int y2){
    return (double)(x1 - x2) * (x1 - x2) + (double)(y1 - y2) * (y1 - y2);
}

int find_set(int x){
    if(x != parents[x]) parents[x] = find_set(parents[x]);
    return parents[x];
}

// 将cover_up和cover_down也合并, 并且如果合并后上下边界都覆盖, 返回true
bool union_set(int x1, int x2){
    int p1 = find_set(x1), p2 = find_set(x2);
    parents[p2] = p1;
    cover_up[p1] |= cover_up[p2];
    cover_down[p1] |= cover_down[p2];
    return cover_up[p1] && cover_down[p1];
}

bool digits_same(double d1, double d2, int precision){
    stringstream stream1, stream2;
    stream1 << fixed << setprecision(4) << d1;
    stream2 << fixed << setprecision(4) << d2;
    return stream1.str() == stream2.str();
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++) cin >> x[i] >> y[i];

    // 计算各点间距离平方
    for(int i = 0; i < k; i++)
        for(int j = i + 1; j < k; j++)
            distance_squares[i][j] = get_distance_square(x[i], y[i], x[j], y[j]);

    double low = 0, high = m / 2.0;

    // 二分法
    while(!digits_same(low, high, PRECISION)){
        double mid = (high + low) / 2, rr = 4 * mid * mid;
        bool can_go_through = true;  // 标记使用mid是否能穿越

        // 初始化并查集
        for(int i = 0; i < k && can_go_through; i++){
            parents[i] = i;
            cover_up[i] = y[i] + mid > m - mid;
            cover_down[i] = y[i] - mid < mid;
            if(cover_up[i] && cover_down[i]) can_go_through = false;
        }

        // 用n^2时间将星球合并, 若合并过程中发现有集合cover_up且cover_down, 则不能穿越
        for(int i = 0; i < k && can_go_through; i++)
            for(int j = i + 1; j < k && can_go_through; j++)
                if(distance_squares[i][j] < rr)
                    if(union_set(i, j))
                        can_go_through = false;

        // 根据结果设置low或high
        if(can_go_through) low = mid;
        else high = mid;
    }

    // 结果保留4位小数
    cout << fixed << setprecision(PRECISION) << low;
}

发表于 2022-08-26 00:53:16 回复(0)

tomjobs

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

const int maxn = 6005 + 7;

struct Point {
    int x, y;
}p[maxn];
int n, m, k;
int fa[maxn];
double dis[maxn][maxn], ans;

double get_dis(Point a, Point b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

int findset(int x) {
    if(fa[x] == x) return x;
    return fa[x] = findset(fa[x]);
}

void merge(int x, int y) {
    int fx = findset(x), fy = findset(y);
    if(fx != fy) {
        fa[fx] = fy;
    }
}

void init() {
    for(int i = 1;i <= k;i++) {
        fa[i] = i;
    }
}

bool check(double distance) {
    init();
    map<int,int>mp;
    for(int i = 1;i <= k;i++) {
        for(int j = i + 1;j <= k;j++) {
            if(dis[i][j] / 2.0 < distance) {
                merge(i, j);
            }
        }
    }
    for(int i = 1;i <= k;i++) {
        if(p[i].y / 2.0 < distance) {
            mp[findset(i)] = 1;
        }
    }
    for(int i = 1;i <= k;i++) {
        if((m - p[i].y) * 1.0 / 2.0 < distance) {
            if(mp.count(findset(i))) {
                return false;
            }
        }
    }
    return true;
}

void solve() {
    double l = 0, r = m / 2.0;
    while(r - l > 1e-7) {
        double mid = (l + r) / 2;
        if(check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    ans = (l + r) / 2.0;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k;i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    for(int i = 1;i <= k;i++) {
        for(int j = i + 1;j <= k;j++) {
            dis[i][j] = get_dis(p[i], p[j]);
        }
    }
    solve();
    printf("%.4f\n", ans);
    return 0;
}

楼上是对的，但是有一些地方冗余了，不需要排序，也不需要扩展域并查集。首先看到最小值最大，就可以想到二分这个最小值，看能否成立。先看点之间能否满足这个最小值，也就是点间距离一般大于等于这个最小值，如果不满足，那么不能从这两点之间穿过，所以用并查集合在一起。被并查集合在一起的点，只能从这些点上面走或者下面走。再看从点下面和上面走是否可行，如果点集不能从上面和下面走，那么这个最小值不成立。

发表于 2021-09-24 17:00:23 回复(1)

C/C++

CcCeLian

#include <bits/stdc++.h>
using namespace std;
const int MAX = 6e3 + 10;
const double e = 1e-6;
struct ind {
    int x, y;
}point[MAX];
int fa[3 * MAX] = { 0 }, ran[3 * MAX] = { 0 }, xvalue[MAX] = { 0 };
int n, m, k, flag;
double dis[MAX][MAX] = { 0 };
double ans = 0;
map<int, int>mapp;
double getDis(ind a, ind b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return pow(dx * dx + dy * dy, 0.5);
}
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (ran[x] <= ran[y]) fa[x] = y;
    else fa[y] = x;
    if (ran[x] == ran[y] && x != y)
        ran[y]++;
}
int check() {
    /*for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            if (find(i + k) == find(j + 2 * k)) return 0;
        }
    }*/
    return flag;
}
void buildDSU(double distance) {
    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k; j++) {
            if (dis[i][j] / 2 < distance) merge(i, j);
        }
    }
    for (int i = 1; i <= k; i++) {
        if ((m - point[i].y) * 1.0 / 2 < distance) {
            merge(i, k + i);
            mapp[find(i)] = 1;
        }
    }
    for (int i = 1; i <= k; i++) {
        if (point[i].y * 1.0 / 2 < distance) {
            merge(i, 2 * k + i);
            if (mapp[find(i)] == 1) {
                flag = 0;
                break;
            }
        }
    }
}
void init() {
    mapp.clear();
    flag = 1;
    for (int i = 1; i <= 3 * k; i++) {
        fa[i] = i;
        ran[i] = 1;
    }
}

bool cmp(ind a, ind b) {
    if (a.x < b.x) return true;
    else return false;
}

void solve() {
    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k; j++) {
            dis[i][j] = getDis(point[i], point[j]);
        }
    }
    double left = 0, right = m * 1.0 / 2, mid;
    while (fabs(left - right) > e) {
        mid = (left + right) / 2;
        init();
        buildDSU(mid);
        if (check()) {
            ans = mid;
            left = mid;
        }
        else right = mid;
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
        scanf_s("%d %d", &point[i].x, &point[i].y);
    sort(point, point + k, cmp);
    for (int i = 1; i <= k; i++)
        xvalue[i] = point[i].x;
    solve();
    printf("%.4f\n", ans);
    return 0;
}

二分+并查集

发表于 2021-09-13 01:03:07 回复(1)