Codeforces77E Martian Food 计算几何+圆的反演

思路:

设两个比较小的圆分别是A,B.

我们将最大圆以及其中一个圆A的交点取出,并以这个点为反演中心,以合适的长度为反演半径,进行反演.

容易发现大圆和A反演之后都成了一条直线.而圆B由于与这两个圆都有唯一交点,那么反演之后也一定都有唯一交点,因此只能是夹在两条直线中间.

不妨以反演中心为原点,三个圆的直径为x轴(方向任意)建立平面直角坐标系,显然B反演之后的圆纵坐标为0.

那么如果我们再放上别的圆(假设一直放在上方),由于它与这三个圆都有唯一交点,所以依然是被卡在两条直线中间,而且在刚才反演的那个圆上方.

这些圆的大小相同,因此我们可以\(O(1)\)得到第\(k\)个圆的圆心半径.

接下来只要再反演回来就好了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef double f2;

struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
}P1,P2;
f2 sqr(const f2&x){return x*x;}
f2 dis(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

inline void GetPointOnDiameter(f2 ox,f2 oy,f2 r,f2 k,f2 b){
    f2 deltax=r/sqrt(k*k+1);
    P1=Point(ox-deltax,k*(ox-deltax)+b);
    P2=Point(ox+deltax,k*(ox+deltax)+b);
}

Point Invert(f2 ox,f2 oy,f2 r,Point A){
    Point o(ox,oy);f2 d=dis(o,A),_d=r*r/d;
    f2 x=ox+(A.x-ox)*(_d/d);
    f2 y=oy+(A.y-oy)*(_d/d);
    return Point(x,y);
}

int main(){
    int Testcase;cin>>Testcase;
    f2 R,r,lx,rx,invr,ox,oy,totalr;int k;
    while(Testcase--){
        scanf("%lf%lf%d",&R,&r,&k);
        invr=r/2;
        rx=invr*invr/(2*r);
        lx=invr*invr/(2*R);
        totalr=(rx-lx)/2,ox=(lx+rx)/2,oy=2*k*totalr;
        GetPointOnDiameter(ox,oy,totalr,oy/ox,0);
        printf("%.10lf\n",dis(Invert(0,0,invr,P1),Invert(0,0,invr,P2))/2);
    }return 0;
}