BUPT2017 wintertraining(15) #5G
HDU - 4773 - 2013 Asia Hangzhou Regional Contest problem D
題意
給定兩個相離的圓，和一個圓外的點P，求過該點和兩個圓都外切的圓。
題解
直接求解聯立的方程組不太可行。需要用一個黑科技——圓的反演。
什麼是圓的反演呢？
假設定圓的圓心為O，半徑是R，線段OP上的點P'滿足\(|OP|\cdot|OP'|=R^2\)，則稱P'是P關于定圓O的反演。
反演的性質：
- 不通過O的直線反演後為通過O的圓
- 不通過O的圓反演後變成不通過O的圓
- 圓C與其反演後的圓C'的切線再反演成的圓C1相切
于是這題就可以 以P為反演中心，反演半徑為1，将兩個圓反演變換為新的兩個圓，将新的兩個圓的外公切線求出來，其中 P與圓心 都在該切線同側的切線 關于P反演變換的圓 就是符合題意的。因為如果是在切線兩側就是内切，如下圖的黑色切線，P點和兩個新的圓的圓心在其兩側，則它的反演的圓将内切C1,C2，題目要我們求的是外切的。紅色的切線反演的圓就是C3。
（順便，畫圖工具扔一下：Desmos）
現在的問題是如何求反演和外公切線。
利用圓上和p最近的點及最遠的點可以求出對應的反演點，它們的距離就是直徑，它們的中點就是圓心，或者圓心可以利用三角函數求得。
外公切線，參照白書P267寫的。
可以根據下面代碼畫圖了解一下。
代碼
#include <cstdio>
#include <algorithm>
#define dd double
#define eps 1e-10
using namespace std;
dd sqr(dd x){return x*x;}
struct cir{
dd x,y,r;
cir(dd _x=0,dd _y=0,dd _r=0):x(_x),y(_y),r(_r){}
void in(int t){scanf("%lf%lf",&x,&y);if(t)scanf("%lf",&r);}
void out(){printf("%f %f %f\n",x,y,r);}
cir point(dd a){//以圓心為原點，a為極角，對應的圓上的點。
return cir(x+r*cos(a),y+r*sin(a));
}
}p,c1,c2,st[5],ed[5];
int cnt;
dd xmult(cir a,cir b,cir o){
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
dd dis(cir a,cir b,cir c){
dd A=b.y-a.y,B=a.x-b.x,C=b.x*a.y-b.y*a.x;
return fabs(A*c.x+B*c.y+C)/sqrt(sqr(A)+sqr(B));
}
dd dis(cir a,cir b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
cir cross(dd a1,dd b1,dd c1,dd a2,dd b2,dd c2){//a1X+b1Y+c1=0和a2X+b2Y+c2=0的交點
dd y=-c1/b1;
if(a1==0)return cir((-c2-b2*y)/a2,y);
y=(a2*c1/a1-c2)/(b2-b1*a2/a1);
return cir(-(c1+b1*y)/a1,y);
}
void inv(cir &c){//圓c反演變換
dd d=dis(c,p),s=sqr(p.r)/(d-c.r),t=sqr(p.r)/(d+c.r);
c.r=(s-t)/2;
c.x=p.x+(c.x-p.x)/d*(t+c.r);
c.y=p.y+(c.y-p.y)/d*(t+c.r);
}
cir inv(cir a,cir b){//直線ab的反演
dd a1=b.y-a.y,b1=a.x-b.x,c1=a.y*b.x-a.x*b.y;//直線ab寫成a1X+b1Y+c=0的形式
cir cr=cross(a1,b1,c1,b1,-a1,a1*p.y-b1*p.x);//p到直線ab的垂足
dd r=sqr(p.r)/dis(a,b,p)/2,d=dis(cr,p);
return cir(p.x+r/d*(cr.x-p.x),p.y+r/d*(cr.y-p.y),r);
}
int sgn(dd a){
return (a>eps)-(a<-eps);
}
bool sameside(cir a,cir b,cir s,cir t){
return sgn(xmult(s,t,a))==sgn(xmult(s,t,b));//利用叉積判斷是否在直線同側
}
void tangent(cir a,cir b){
cnt=0;
dd base=atan2(b.y-a.y,b.x-a.x),d=dis(a,b),ang=acos((a.r-b.r)/d);
//這裡因為寫成a.y-b.y,a.x-b.x而wa了，畫了下圖就明白了
st[cnt]=a.point(base-ang),ed[cnt]=b.point(base-ang);
if(sameside(p,a,st[cnt],ed[cnt]))cnt++;//p和圓心在切線的同側
st[cnt]=a.point(base+ang),ed[cnt]=b.point(base+ang);
if(sameside(p,a,st[cnt],ed[cnt]))cnt++;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
c1.in(1);c2.in(1);p.in(0);p.r=1;
inv(c1);inv(c2);//c1,c2關于p反演
tangent(c1,c2);//求外公切線
printf("%d\n",cnt);
for(int i=0;i<cnt;i++)inv(st[i],ed[i]).out();//外公切線關于p反演後的圓
}
return 0;
}
┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆ ┆可┆有┆謙┆戮┆那┆ ┆大┆始┆ ┆然┆
┆薄┆一┆臨┆你┆的┆還┆沒┆ ┆來┆ ┆是┆來┆遜┆沒┆些┆ ┆雁┆終┆ ┆而┆
┆ ┆暖┆ ┆如┆地┆站┆有┆ ┆也┆ ┆我┆ ┆的┆有┆精┆ ┆也┆沒┆ ┆你┆
┆ ┆這┆ ┆試┆方┆在┆逃┆ ┆會┆ ┆在┆ ┆清┆來┆準┆ ┆沒┆有┆ ┆沒┆
┆ ┆生┆ ┆探┆ ┆最┆避┆ ┆在┆ ┆這┆ ┆晨┆ ┆的┆ ┆有┆來┆ ┆有┆
┆ ┆之┆ ┆般┆ ┆不┆ ┆ ┆這┆ ┆裡┆ ┆沒┆ ┆殺┆ ┆來┆ ┆ ┆來┆