Gym - 101617F :Move Away (圆的交点)

pro:给定N个圆,求离原点最远的点,满足它在N个圆里。输出这个距离。N<50;

sol:关键点一定是圆与圆的交点。 圆与 圆心到原点的直线 的交点。 然后去验证这些关键点是否在N个圆内。 实际操作的时候需要考虑一些条件:

1,求圆的交点的时候,先判断是否内含或者相离。

2,求直线与圆的交点的时候,先判断是否圆心就在原点处。

3,有可能不存在相交的圆。

如何求圆与圆的交点:

用atan2求出t,余弦定理求出a,即可。

Gym - 101617F :Move Away (圆的交点)

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const double eps=1e-;
const double pi=acos(-1.0);
struct point{
double x,y;
point(){}
point(double xx,double yy):x(xx),y(yy){}
};
struct Circle{
point c;
double r;
};
point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y);}
point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y);}
point operator *(point a,double p){return point(a.x*p,a.y*p);}
point operator /(point a,double p){ return point(a.x/p,a.y/p);}
double dot(point a,point b){ return a.x*b.x+a.y*b.y;}
double det(point a,point b){ return a.x*b.y-a.y*b.x;}
Circle C[maxn]; point P[maxn]; int tot,N; double ans1,ans2;
void CirintersectCir(Circle A,Circle B)
{
point L=B.c-A.c;
double dis=sqrt(dot(L,L));
if(dis>A.r+B.r||fabs(A.r-B.r)>=dis+eps) return ;
double angle1=atan2(L.y,L.x);
double angle2=acos((A.r*A.r+dis*dis-B.r*B.r)/(*A.r*dis));
P[++tot]=point(A.c.x+A.r*cos(angle1+angle2),A.c.y+A.r*sin(angle1+angle2));
P[++tot]=point(A.c.x+A.r*cos(angle1-angle2),A.c.y+A.r*sin(angle1-angle2));
}
void OtoCir(Circle A)
{
double dis=sqrt(dot(A.c,A.c));
P[++tot]=A.c+A.c*A.r/dis;
}
int fcy=; double R;
bool check(point p)
{
rep(i,,N)
if(sqrt(dot(p-C[i].c,p-C[i].c))>C[i].r+eps) return false;
if(fcy&&sqrt(dot(p,p))>R+eps) return false;
return true;
}
int main()
{
scanf("%d",&N);
rep(i,,N){
scanf("%lf%lf%lf",&C[i].c.x,&C[i].c.y,&C[i].r);
if(C[i].c.x==0.0&&C[i].c.y==0.0) {
if(fcy==) fcy=,R=C[i].r;
else R=min(R,C[i].r);
if(ans1==) ans1=C[i].r;
else ans2=min(ans2,C[i].r);
i--; N--;
}
}
if(fcy){
Circle T; T.r=R; T.c.x=T.c.y=;
rep(i,,N){
P[++tot]=C[i].c/sqrt(dot(C[i].c,C[i].c))*R;
CirintersectCir(T,C[i]);
}
}
rep(i,,N)
rep(j,i+,N)
CirintersectCir(C[i],C[j]);
rep(i,,N) OtoCir(C[i]);
rep(i,,tot)
if(check(P[i]))
ans2=max(ans2,sqrt(dot(P[i],P[i])));
if(ans2!=0.0) printf("%.3lf\n",ans2);
else printf("%.3lf\n",ans1);
return ;
}
上一篇:Atitit 快速开发体系建设路线图


下一篇:JSM的topic和queue的区别