[LOJ 2190] 「SHOI2014」信号增幅仪

链接

链接

题解

坐标系直到 \(x\) 轴与椭圆长轴平行

点的坐标变换用旋转公式就可以了

因为是椭圆，所以所有点横坐标除以 \(p\)

然后最小圆覆盖

代码

#include<bits/stdc++.h>

#define N 50005

using namespace std;

int n,deg,p;double r;

const double pi=acos(-1);

struct P{

    double x,y;

    P operator - (const P &b)const{return (P){x-b.x,y-b.y};}

}a[N],c;

P rotate(P t,int tmp){

    double rt=1.0*tmp/180*pi;P ret;

    ret.x=t.x*cos(rt)-t.y*sin(rt);

    ret.y=t.x*sin(rt)+t.y*cos(rt);

    return ret;

}

double len(P a){return sqrt(a.x*a.x+a.y*a.y);}

P getcentre(P A,P B,P C){

    double a1=B.x-A.x,b1=B.y-A.y,c1=(a1*a1+b1*b1)/2;

    double a2=C.x-A.x,b2=C.y-A.y,c2=(a2*a2+b2*b2)/2;

    double d=a1*b2-b1*a2;P ret;

    ret.x=A.x+(c1*b2-c2*b1)/d;

    ret.y=A.y+(c2*a1-c1*a2)/d;

    return ret;

}

void getcircle(){

    random_shuffle(a+1,a+1+n);

    c=a[1];r=0;

    for(int i=1;i<=n;i++){

        if(len(a[i]-c)<=r)continue;

        c=a[i];r=0;

        for(int j=1;j<i;j++){

            if(len(a[j]-c)<=r)continue;

            c.x=(a[i].x+a[j].x)/2;

            c.y=(a[i].y+a[j].y)/2;

            r=len(a[j]-c);

            for(int k=1;k<j;k++){

                if(len(a[k]-c)<=r)continue;

                c=getcentre(a[i],a[j],a[k]);

                r=len(a[i]-c);

            }

        }

    }

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    scanf("%lf%lf",&a[i].x,&a[i].y);

    scanf("%d%d",&deg,&p);

    for(int i=1;i<=n;i++)

    a[i]=rotate(a[i],-deg),a[i].x/=p;

    getcircle();printf("%.3lf\n",r);

    return 0;

}