CF333E 题解

Others · 2022-02-11 11:22:35 · 题解

这题很有技巧。

首先是求最大的圆的半径，因为这里没有边界，所以圆的半径只与三个点间的距离相关，用心想想当两个圆相切时半径肯定最大，而三点间有三个距离，我们肯定取最小的。

然后就是哪三个点，看到 n 的范围是 n\le3000，所以先想到的肯定是 O(n^2)，就是枚举两个点然后决定第三个点，因为第三个点不确定，所以三个点间最短距离我们期望是确定的两点间的最短距离，这要求第三个点和这两个点的距离均大于这两个点的距离，而且我们需要快速地求出第三个点存不存在（小于 O(n)）。

我们将每两个点间的距离预处理，然后从大到小枚举，每次将两个点互相连边，在枚举到一条边时就只需要判断之前有没有一个点同时与这两个点连边，这东西我们维护一个 bitset 来优化一个 w。

总时间复杂度 O(\frac{n^3}{w})。

code

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=3001;
struct Node{
    int x, y;
    inline int get_long(const Node &p)const{return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);}
}a[3005];
struct node{
    int x, y, z;
    inline bool operator<(const node &p)const{return z > p.z;}
};
vector<node> vec;
int n;
bitset<3005> edge[3005],tmp;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a[i].x, &a[i].y);
        for(int j = i - 1; j; j--){
            vec.push_back(node{i, j, a[i].get_long(a[j])});
        }
    }
    stable_sort(vec.begin(), vec.end());
    for(auto &p: vec) {
        edge[p.x][p.y] = 1, edge[p.y][p.x] = 1;
        if((edge[p.x]&edge[p.y]).any()) {
            printf("%.20lf", sqrt(p.z) / 2.0);
            return 0;
        }
    }
    return 0;
}