適用題目特征

題目中存在多個圓/直線之間的相切關(guān)系的情況，可利用反演簡化計算。

原理

1 圓A外的點的反演點在圓A內(nèi)，反之亦然；圓A上的點的反演點為其自身。
2 不過點P的圓A，其反演圖形是不過點P的圓。
3 過點P的圓A，其反演圖形是不過點P的直線。
4 兩個圖形相切，則他們的反演圖形也相切。

例題

HDU 4774
代碼如下

/*
HDU 4773 
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=4;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
struct Point{
    double x,y;
    Point(double _x=0,double _y=0):x(_x),y(_y){}
    const bool operator<(const Point &h) const{return (x<h.x)||(x==h.x&&y<h.y);}
};
typedef Point Vec;
Vec operator+(Vec a,Vec b){
    return Vec(a.x+b.x,a.y+b.y);
}
Vec operator-(Vec a,Vec b){
    return Vec(a.x-b.x,a.y-b.y);
}   
Vec operator*(Vec a,double p){
    return Vec(a.x*p,a.y*p);
}
Vec operator/(Vec a,double p){
    return Vec(a.x/p,a.y/p);
}
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
double dot(Vec a,Vec b){
    return a.x*b.x+a.y*b.y;
}
double len(Vec a){
    return sqrt(dot(a,a));
}
double cross(Vec a,Vec b){
    return a.x*b.y-a.y*b.x;
}
Point getLineProjection(Point p,Point a,Point b){
    Vec v=b-a;
    return a+v*(dot(v,p-a)/dot(v,v));
}
struct Circle{
    Point c;double r;
    Circle():c(Point(0,0)),r(0){}
    Circle(Point _c,double _r=0):c(_c),r(_r){}
    Point point(double a){
        return Point(c.x+cos(a)*r,c.y+sin(a)*r);
    }
};
int getTangents(Circle A,Circle B,Point *a,Point *b){
    int cnt=0;
    if(A.r<B.r){swap(A,B);swap(a,b);}
    double d2=((A.c.x-B.c.x)*(A.c.x-B.c.x)+(A.c.y-B.c.y)*(A.c.y-B.c.y));
    double rdiff=A.r-B.r;
    double rsum=A.r+B.r;
    if(dcmp(d2-rdiff*rdiff)<0) return 0;
    double base=atan2(B.c.y-A.c.y,B.c.x-A.c.x);
    if(dcmp(d2)==0&&dcmp(A.r-B.r)==0) return -1;
    if(dcmp(d2-rdiff*rdiff)==0){
        a[cnt]=A.point(base),b[cnt]=B.point(base),cnt++;return 1;
    }
    double ang=acos(rdiff/sqrt(d2));
    a[cnt]=A.point(base+ang),b[cnt]=B.point(base+ang),++cnt;
    a[cnt]=A.point(base-ang),b[cnt]=B.point(base-ang),++cnt;
    if(dcmp(d2-rsum*rsum)==0){
        a[cnt]=A.point(base),b[cnt]=B.point(pi+base),++cnt; 
    } 
    else if(dcmp(d2-rsum*rsum)>0){
        double ang=acos(rsum/sqrt(d2));
        a[cnt]=A.point(base+ang),b[cnt]=B.point(pi+base+ang),++cnt;
        a[cnt]=A.point(base-ang),b[cnt]=B.point(pi+base-ang),++cnt;
    }
    return cnt;
}
Circle Inversion_C2C(Point O,double R,Circle A){
    double OA=len(A.c-O);
    double RB = 0.5 * ((1 / (OA - A.r)) - (1 / (OA + A.r))) * R * R;
    double OB = OA * RB / A.r;
    double Bx = O.x + (A.c.x - O.x) * OB / OA;
    double By = O.y + (A.c.y - O.y) * OB / OA;
    return Circle(Point(Bx, By), RB);
}
Circle Inversion_L2C(Point O,double R,Point A,Vec v) {
    Point P=getLineProjection(O,A,A+v);
    double d=len(O-P);
    double RB=R*R/(2*d);
    Vec VB=(P-O)/d*RB;
    return Circle(O+VB,RB);
}  
bool theSameSideOfLine(Point A,Point B,Point S,Vec v) {
    return dcmp(cross(A-S,v))*dcmp(cross(B-S,v))>0;
} 
int T;
void solve(){
    Circle A,B;Point P;
    cin>>A.c.x>>A.c.y>>A.r;
    cin>>B.c.x>>B.c.y>>B.r;
    cin>>P.x>>P.y;
    Circle NA=Inversion_C2C(P,10,A);
    Circle NB=Inversion_C2C(P,10,B);
    Point LA[maxn],LB[maxn];
    Circle ansC[maxn];
    int q=getTangents(NA,NB,LA,LB),ans=0;
    rep0(i,0,q){
        if(theSameSideOfLine(NA.c,NB.c,LA[i],LB[i]-LA[i])){
            if(!theSameSideOfLine(P,NB.c,LA[i],LB[i]-LA[i])) continue;
            ansC[ans++]=Inversion_L2C(P,10,LA[i],LB[i]-LA[i]);
        }
    } 
    cout<<ans<<endl;
    rep0(i,0,ans) printf("%.8lf %.8lf %.8lf\n",ansC[i].c.x,ansC[i].c.y,ansC[i].r);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("Problem of Apollonius.in","r",stdin);
    cin>>T;
    while(T--) solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif