C++ 解法, 执行用时: 78ms, 内存消耗: 1196K, 提交时间: 2022-06-21 21:59:45

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<double, double> PDD;
const int maxn = 50010;
const double eps = 1e-8;
const double pi = acos(-1);
typedef struct node
{
    PDD p;
    double r;
}Circle;
PDD q[maxn];
int n;
int sign(double x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}
int dcmp(double x, double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}
PDD operator + (PDD a, PDD b)
{
    return {a.x + b.x, a.y + b.y};
}
PDD operator - (PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}
double operator * (PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}
PDD operator * (PDD a, double t)
{
    return {a.x * t, a.y * t};
}
PDD operator / (PDD a, double b)
{
    return {a.x / b, a.y / b};
}
double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}
PDD rotate(PDD a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}
pair<PDD, PDD> get_line(PDD a, PDD b)
{
    return {(a + b) / 2, rotate(b - a, pi / 2)};
}
Circle get_circle(PDD a, PDD b, PDD c)
{
    auto u = get_line(a, b), v = get_line(a, c);
    auto p = get_line_intersection(u.x, u.y, v.x, v.y);
    return {p, get_dist(p, a)};
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i].x >> q[i].y;
    double theta, p; cin >> theta >> p;
    for(int i = 0; i < n; i ++){
        q[i] = rotate(q[i], theta / 180 * pi);
        q[i].x /= p;
    }
    random_shuffle(q, q + n);
    Circle c({q[0], 0});
    for(int i = 1; i < n; i ++){
        if(dcmp(c.r, get_dist(c.p, q[i])) < 0){
            c = {q[i], 0};
            for(int j = 0; j < i; j ++){
                if(dcmp(c.r, get_dist(c.p, q[j])) < 0){
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2};
                    for(int k = 0; k < j; k ++){
                        if(dcmp(c.r, get_dist(c.p, q[k])) < 0){
                            c = get_circle(q[i], q[j], q[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.3lf\n", c.r);
    return 0;
}