適用題目特征
題目中存在多個(gè)圓/直線之間的相切關(guān)系的情況丁稀，可利用反演簡化計(jì)算。
原理
1 圓A外的點(diǎn)的反演點(diǎn)在圓A內(nèi)话原，反之亦然夕吻；圓A上的點(diǎn)的反演點(diǎn)為其自身诲锹。
2 不過點(diǎn)P的圓A，其反演圖形是不過點(diǎn)P的圓涉馅。
3 過點(diǎn)P的圓A归园，其反演圖形是不過點(diǎn)P的直線。
4 兩個(gè)圖形相切稚矿，則他們的反演圖形也相切庸诱。
例題
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
