[BZOJ 3564] [SHOI2014] 信号增幅仪 【最小圆覆盖】

时间:2021-04-09 14:38:03

题目链接:BZOJ - 3564

题目分析

求最小椭圆覆盖,题目给定了椭圆的长轴与 x 轴正方向的夹角,给定了椭圆长轴与短轴的比值。

那么先将所有点旋转一个角度,使椭圆长轴与 x 轴平行,再将所有点的 x 坐标除以长轴与短轴的比值,然后就直接做最小圆覆盖了。

随机增量法,一定别忘了 random_shuffle 。

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; #define PI 3.14159265358979323846
#define Vector Point typedef double LF; const int MaxN = 50000 + 5; const LF Eps = 1e-9; int n; LF Alpha, SinA, CosA; struct Point
{
LF x, y; Point() {}
Point(LF a, LF b)
{
x = a; y = b;
} void Rotate(LF SinA, LF CosA)
{
LF tx, ty;
tx = CosA * x - SinA * y;
ty = SinA * x + CosA * y;
x = tx; y = ty;
}
} P[MaxN]; inline LF Sqr(LF x) {return x * x;} inline LF Dis(Point p1, Point p2)
{
return sqrt(Sqr(p1.x - p2.x) + Sqr(p1.y - p2.y));
} Point operator + (Point p1, Point p2) {return Point(p1.x + p2.x, p1.y + p2.y);}
Point operator - (Point p1, Point p2) {return Point(p1.x - p2.x, p1.y - p2.y);}
Point operator * (Point p, LF t) {return Point(p.x * t, p.y * t);}
Point operator / (Point p, LF t) {return Point(p.x / t, p.y / t);} struct Line
{
Point p;
Vector v; Line() {}
Line(Point p1, Point p2)
{
p = p1;
v = p2 - p1;
}
} L1, L2; struct Circle
{
Point o;
LF r; bool InCircle(Point p)
{
return Dis(o, p) <= r + Eps;
}
} C; inline LF Cross(Vector v1, Vector v2)
{
return v1.x * v2.y - v2.x * v1.y;
} Point Intersection(Line l1, Line l2)
{
Vector u = l2.p - l1.p;
LF t = Cross(u, l2.v) / Cross(l1.v, l2.v);
return l1.p + (l1.v * t);
} Vector Turn90(Vector v)
{
return Vector(-v.y, v.x);
} Line Verticle(Point p1, Point p2)
{
Line ret;
ret.p = (p1 + p2) / 2.0;
ret.v = Turn90(p2 - p1);
return ret;
} int main()
{
srand(51405102);
scanf("%d", &n);
int a, b;
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &a, &b);
P[i] = Point((LF)a, (LF)b);
}
random_shuffle(P + 1, P + n + 1);
int ad, p;
scanf("%d", &ad);
Alpha = (LF)(-ad) / (LF)180 * PI;
SinA = sin(Alpha); CosA = cos(Alpha);
scanf("%d", &p);
for (int i = 1; i <= n; ++i)
{
P[i].Rotate(SinA, CosA);
P[i].x /= (LF)p;
}
C.o = P[1]; C.r = 0;
for (int i = 1; i <= n; ++i)
{
if (C.InCircle(P[i])) continue;
C.o = P[i]; C.r = 0;
for (int j = 1; j < i; ++j)
{
if (C.InCircle(P[j])) continue;
C.o = (P[i] + P[j]) / 2.0;
C.r = Dis(C.o, P[j]);
for (int k = 1; k < j; ++k)
{
if (C.InCircle(P[k])) continue;
L1 = Verticle(P[i], P[k]);
L2 = Verticle(P[j], P[k]);
C.o = Intersection(L1, L2);
C.r = Dis(C.o, P[k]);
}
}
}
printf("%.3lf\n", C.r);
return 0;
}