$\leftarrow$ 码字、码代码不易,给个赞吧
我们尝试把这道题转化为模板题
我们发现这道题只多了两个数,旋转角度和拉长倍数,我们可以将所有点和椭圆(信号覆盖区域)顺时针旋转 $a$ 度,然后更新点的坐标。
接下来处理拉长倍数,更新坐标后我们可以将每个点的 $x$ 坐标除以拉长倍数 $p$ ,得到的点求一遍最小圆覆盖即可
注意这道题用 double
会被卡精度,要用 long double
代码:
#include<bits/stdc++.h>
#define p2(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef long double db;
struct Point{db x, y;};
struct Vector{Point a, b;};
const int N = 1e5 + 5;
Point a[N], circleCenter;
db angle, p, circleR;
int n;
Point operator*(db t, Vector u)
{
return {t * (u.b.x - u.a.x), t * (u.b.y - u.a.y)};
}
Point operator+(Point a, Point b)
{
return {a.x + b.x, a.y + b.y};
}
Point getmid(Vector u)
{
return {(u.a.x + u.b.x) / 2 , (u.a.y + u.b.y) / 2};
}
db getdis(Point a, Point b)
{
return sqrt(p2(a.x - b.x) + p2(a.y - b.y));
}
bool incircle(Point circleCenter, db r, Point a)
{
return getdis(circleCenter, a) <= r;
}
db cross(db x1, db y1, db x2, db y2)
{
return x1 * y2 - x2 * y1;
}
db cross(Vector u, Vector v)
{
return cross(u.b.x - u.a.x, u.b.y - u.a.y, v.b.x - v.a.x, v.b.y - v.a.y);
}
Point getLineIntersection(Point p, Vector u, Point q, Vector v)
{
Vector w = {q, p};
db t = cross(v, w) / cross(u, v);
return p + t * u;
}
Point getLineIntersection(Vector u, Vector v)
{
return getLineIntersection(u.a, u, v.a, v);
}
Point getCircleCenter(Point a, Point b, Point c)
{
Vector v1 = {a, b}, v2 = {a, c};
Point mid1 = getmid(v1), mid2 = getmid(v2);
db k1 = atan2(v1.b.y - v1.a.y, v1.b.x - v1.a.x);
db k2 = atan2(v2.b.y - v2.a.y, v2.b.x - v2.a.x);
k1 += acos(-1) / 2, k2 += acos(-1) / 2;
Vector r1 = {mid1, {mid1.x + 1, mid1.y + tan(k1)}};
Vector r2 = {mid2, {mid2.x + 1, mid2.y + tan(k2)}};
return getLineIntersection(r1, r2);
}
Point rotate(Point a, db angle)
{
db dis = getdis({0,0}, a);
angle = angle - atan2(a.y, a.x);
a.x = cos(angle) * dis;
a.y = sin(angle) * dis;
return a;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%Lf%Lf", &a[i].x, &a[i].y);
scanf("%Lf%Lf", &angle, &p);
angle = angle * (2.0 * acos(-1)) / 360;
for(int i = 1; i <= n; i++)
{
a[i] = rotate(a[i], angle);
a[i].x /= p;
}
random_shuffle(a + 1, a + n + 1);
for(int i = 2; i <= n; i++)
{
if(i == 2 || !incircle(circleCenter, circleR, a[i]))
{
circleR = getdis(a[i], a[1])/2;
circleCenter = getmid({a[i], a[1]});
for(int j = 2; j < i; j++)
{
if(!incircle(circleCenter, circleR, a[j]))
{
circleR = getdis(a[i], a[j]) / 2;
circleCenter = getmid({a[i], a[j]});
for(int k = 1; k < j; k++)
{
if(!incircle(circleCenter, circleR, a[k]))
{
circleCenter = getCircleCenter(a[i], a[j], a[k]);
circleR = getdis(circleCenter, a[i]);
}
}
}
}
}
}
printf("%.3Lf", circleR);
return 0;
}