#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 100010;
const double eps = 1e-8, pi = acos(-1);
int n;
PDD q[N];
struct CIRCLE { PDD p; double r; };
int cmp(double x, double y) { return (fabs(x - y) < eps) ? 0 : (x < y) ? -1 : 1; };
PDD operator-(PDD a, PDD b) { return make_pair(a.x - b.x, a.y - b.y); };
PDD operator+(PDD a, PDD b) { return make_pair(a.x + b.x, a.y + b.y); };
PDD operator*(PDD a, double t) { return make_pair(a.x * t, a.y * t); };
PDD operator/(PDD a, double t) { return make_pair(a.x / t, a.y / t); };
double operator*(PDD a, PDD b) { return a.x * b.y - a.y * b.x; };
PDD rotate(PDD a, double b) { return make_pair(a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)); };
PDD get_intersection(PDD p, PDD v, PDD q, PDD w) { return p + v * (w * (p - q) / (v * w)); }
pair<PDD, PDD> get_line(PDD a, PDD b) { return make_pair((a + b) / 2, rotate(b - a, pi / 2)); };
double get_dist(PDD a, PDD b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); };
CIRCLE get_circle(PDD a, PDD b, PDD c) {
pair<PDD, PDD> u = get_line(a, b), v = get_line(a, c);
PDD p = get_intersection(u.x, u.y, v.x, v.y);
return (CIRCLE) { p, get_dist(p, a) };
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
random_shuffle(q, q + n);
CIRCLE c = (CIRCLE) { q[0], 0 };
for (int i = 1; i < n; i++)
if (cmp(c.r, get_dist(c.p, q[i])) < 0) {
c = (CIRCLE) { q[i], 0 };
for (int j = 0; j < i; j++)
if (cmp(c.r, get_dist(c.p, q[j])) < 0) {
c = (CIRCLE) { (q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2 };
for (int k = 0; k < j; k++)
if (cmp(c.r, get_dist(c.p, q[k])) < 0)
c = get_circle(q[i], q[j], q[k]);
}
}
printf("%.10lf\n%.10lf %.10lf", c.r, c.p.x, c.p.y);
return 0;
}
不是很明白这里时间复杂度的求法
‘’‘
for(int i = 2; i <= n; i++)
‘’‘
不应该第一层循环i的时间复杂度是O(n)吗,代码里的i可是实打实的会从2枚举到n啊