暑假集训系列题解（十五）

暑假集训系列题解（十五）

题目1

题目链接

问题 C: Safe Distance

题目描述

The past year has been difficult, with a virus spreading among the population. Fortunately, Alice knows that one of the keys to be healthy is to keep a safe distance from other people.

Alice is currently in a closed room, represented in the 2D plane, with width X and height Y. There are N other people inside the room, and we’re given their (xi, yi) coordinates.

We consider Alice and the N people as points in the 2D plane. Alice’s initial position is (0, 0) and she wants to move to the exit at position (X, Y). She can move freely in any direction inside the room,but can not step outside the room bounds.

Find the maximum distance Alice can keep from other people while moving from (0, 0) to (X, Y).

输入

The input begins with one line containing two space-separated integers, X and Y, where X is the width, and Y is the height of the room. The second line consists of a single integer N, the number of people in the room. Then N lines follow, each of them consisting of two floating-point numbers xi and yi, the coordinates of the ith person in the room.

• 1≤X, Y≤1 000 000

• 1≤N≤1 000

• 0≤xi≤X

• 0≤yi≤Y

输出

The output consists of a single value d, the maximum safe distance, as a floating-point number. An additive or multiplicative error of 10−5 is tolerated: if d is the answer, any number either within [d − $10^{−5}$; d + $10^{−5}$] or within [(1 −$10^{−5}$)d; (1 +$10^{−5}$)d] is accepted.

样例输入

8 6
3
3 1
3 5.5
6.5 1.5

样例输出

2.250000

提示

Alice can keep a distance of 2.25 from every other person, and this is the best she can do. The picture below shows a possible path (in green).

题解

并查集题目，将左和上面的两条边看作起点，将右和下面的两条边看作终点，如果起点和终点相互连通，则S和F点将无法连通。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int from, to;
    double val;
};
vector<node> v;
int fa[100500] = {0};
double xx[100500] = {0}, yy[100500] = {0};
int findfa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findfa(fa[x]);
}
bool cmp(node a, node b)
{
    return a.val < b.val;
}
int main()
{
    double x, y;
    scanf("%lf%lf", &x, &y);
    int n;
    scanf("%d", &n);
    int s = n + 1, e = n + 2;
    fa[s] = s, fa[e] = e;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        scanf("%lf%lf", &xx[i], &yy[i]);
        v.push_back({s, i, min(xx[i], y - yy[i])});
        v.push_back({e, i, min(x - xx[i], yy[i])});
        for (int j = 1; j < i; j++)
            v.push_back({i, j, sqrt((xx[i] - xx[j]) * (xx[i] - xx[j]) + (yy[i] - yy[j]) * (yy[i] - yy[j])) / 2.0});
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++)
    {
        int fx = findfa(v[i].from);
        int fy = findfa(v[i].to);
        if (fx == fy)
            continue;
        fa[fx] = fy;
        if (findfa(s) == findfa(e))
        {
            printf("%.8f\n", v[i].val);
            return 0;
        }
    }
}