bzoj 3564 信号增幅仪

• 一道有意义的好题.启发我们善用坐标变换,如在遇到椭圆时使用坐标变换转化为圆来处理.
• 直接在一个方向上进行伸缩不方便,先将坐标系旋转,使椭圆长轴与 \(x\) 轴平行,点的坐标变换用旋转公式处理.
• 坐标系逆时针转过了 \(\theta\) ,相当于点逆时针转过了 \(-\theta\) .
• 再沿长轴方向伸缩,将点的横坐标除以 \(p\) ,椭圆就转化为了圆,求一个最小圆覆盖即可.

#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pii pair<int,int> inline int read() { int x=0; bool pos=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return pos?x:-x; } struct v2{ double x,y; v2(double x=0,double y=0):x(x),y(y) {} v2 operator + (const v2 &rhs) const { return v2(x+rhs.x,y+rhs.y); } v2 operator / (const double &rhs) const { return v2(x/rhs,y/rhs); } v2 operator - (const v2 &rhs) const { return v2(x-rhs.x,y-rhs.y); } double operator * (const v2 &rhs) const { return x*rhs.y-y*rhs.x; } double modulus() { return sqrt(x*x+y*y); } }; const double PI=acos(-1.0); v2 rotate(v2 v,double degree) { double rad=degree/180*PI; //v2 res=v2(cos(rad)*v.x-sin(rad)*v.y,sin(rad)*v.x+cos(rad)*v.y); v2 res=v2(v.x*cos(rad)-v.y*sin(rad),v.x*sin(rad)+v.y*cos(rad)); return res; } const int MAXN=5e4+10; int n; v2 a[MAXN]; double theta,p; void transform() { for(int i=1;i<=n;++i) { a[i]=rotate(a[i],theta); a[i].x/=p; } } const double eps=1e-9; int dcmp(double x) { return fabs(x)<eps?0:(x>0?1:-1); } v2 getcentre(v2 a,v2 b,v2 c) { v2 centre; double a1=b.x-a.x; double b1=b.y-a.y; double c1=(a1*a1+b1*b1)/2.0; double a2=c.x-a.x; double b2=c.y-a.y; double c2=(a2*a2+b2*b2)/2.0; double d=a1*b2-a2*b1; centre.x=a.x+(c1*b2-c2*b1)/d; centre.y=a.y+(a1*c2-a2*c1)/d; return centre; } bool incir(v2 centre,double r,v2 p) { return dcmp((p-centre).modulus()-r)<=0; } double MinCircleCover() { srand(19260817); random_shuffle(a+1,a+1+n); v2 centre=a[1]; double r=0; for(int i=2;i<=n;++i) { if(!incir(centre,r,a[i])) { centre=a[i]; r=0; for(int j=1;j<i;++j) { if(!incir(centre,r,a[j])) { centre=(a[i]+a[j])/2.0; r=(a[i]-centre).modulus(); for(int k=1;k<j;++k) { if(!incir(centre,r,a[k])) { centre=getcentre(a[i],a[j],a[k]); r=(a[i]-centre).modulus(); } } } } } } return r; } int main() { n=read(); for(int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y); scanf("%lf%lf",&theta,&p); theta*=-1; transform(); double ans=MinCircleCover(); printf("%.3lf\n",ans); return 0; }

转载于:https://www.cnblogs.com/jklover/p/10388854.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/98768809

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。