题解 UVA10674 【Tangents】
ChthollyTree
2019-01-26 14:49:46
最近在学计算几何，照着lrj的蓝书打的
题意：给定两个圆，求它们的公切线
两个圆的公切线与圆的位置有关
可以通过圆心距离和圆的半径确定两圆的位置关系
（圆心距d , 两圆半径 r1 r2 ，设r1 > r2）
1.两圆重合 无数个公切线(d = 0, r1 = r2)
2.两圆内含，0个公切线(d < r1 - r2)
3.两圆内切，1个公切线(d = r1 - r2)
4.两圆相交，2个外公切线(r1-r2 < d < r1 + r2)
5.两圆外切，2个外公切线，1个内公切线(d = r1 + r2)
6.两圆相离，2个外公切线，2个内公切线(d > r1 + r2)
两圆相切的情况，可以连接圆心，过切点然后求出切点坐标可以求出3和5的内切线
接下来就是求4,5,6外切线和4，6内切线
下面有两张相离时刻的图，但其他情况也一样
就可以算出连心线与圆心到切点的夹角
也就可以算出圆心到切点的极角
也就可以求出切点
代码，较丑，勿喷
```
#include<bits/stdc++.h>
using namespace std;
#define db double
#define esp 1e-8
#define xl dian
const db pi = acos(-1);
struct dian {
db x,y;
void wt()
{
printf("%.5lf %.5lf ",x,y);
}
};
struct yuan
{
dian o;
db r;
dian yp(db a) {
return (dian){o.x + r*cos(a),o.y + r*sin(a)};
}
};
int dcmp(db a) {
if(fabs(a) < esp) return 0;
if(a > 0) return 1;
else return -1;
}
dian operator +(dian a,xl b) {
return (dian){a.x + b.x,a.y + b.y};
}
dian operator -(dian a,dian b) {
return (dian){a.x - b.x,a.y - b.y};
}
xl operator *(dian a,db b) {
return (xl){a.x*b,a.y*b};
}
xl operator /(dian a,db b) {
return (xl){a.x/b,a.y/b};
}
db chaji(xl a,xl b) {
return a.x * b.y - a.y*b.x;
}
db dianji(xl a,xl b) {
return a.x * b.x + a.y * b.y;
}
db jijiao(xl a){return atan2(a.y,a.x);}
db chang(xl a) {
return dianji(a,a);
}
bool operator <(dian a,xl b)
{
return dcmp(a.x-b.x)==-1 || (dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == -1);
}
yuan a,b;
int T,n;
struct QAQ
{
dian a;
dian b;
} s[6];
bool cmp(QAQ a,QAQ b)
{
return a.a < b.a;
}
int gqx(yuan A,yuan B)
{
int cnt = 0;
bool fl = 0;
if(dcmp(A.r - B.r) == -1) {
swap(A,B);
fl = 1;
}
db d = chang(A.o - B.o);
db rd = A.r - B.r,rs = A.r + B.r;
if(dcmp(d - rd*rd) == -1) return 0;
db ba = jijiao(B.o - A.o);
if(dcmp(d) == 0 && dcmp(A.r - B.r) == 0) return -1;
if(dcmp(d - rd*rd) == 0) {
cnt = 1;
s[cnt].a = A.yp(ba);
s[cnt].b = B.yp(ba);
return cnt;
}
db ang = acos((A.r - B.r) / sqrt(d));
cnt ++;
s[cnt].a = A.yp(ba + ang);
s[cnt].b = B.yp(ba + ang);
cnt ++;
s[cnt].a = A.yp(ba - ang);
s[cnt].b = B.yp(ba - ang);
if(dcmp(d - rs*rs) == 0) {
cnt ++;
s[cnt].a = A.yp(ba);
s[cnt].b = B.yp(pi + ba);
} else if(dcmp(d - rs*rs) == 1) {
ang = acos((A.r + B.r)/sqrt(d));
cnt ++;
s[cnt].a = A.yp(ba + ang);
s[cnt].b = B.yp(pi + ba + ang);
cnt ++;
s[cnt].a = A.yp(ba - ang);
s[cnt].b = B.yp(pi + ba - ang);
}
if(fl)
{
for(int i = 1; i <= cnt; i ++)
swap(s[i].a,s[i].b);
}
sort(s+1,s+cnt + 1,cmp);
return cnt;
}
int main()
{
while(1)
{
scanf("%lf%lf%lf",&a.o.x,&a.o.y,&a.r);
scanf("%lf%lf%lf",&b.o.x,&b.o.y,&b.r);
if(dcmp(a.o.x) == 0 && dcmp(a.o.y) == 0 && dcmp(a.r) == 0 \
&& dcmp(b.o.x) == 0 && dcmp(b.o.y) == 0 && dcmp(b.r) == 0) return 0;
n = gqx(a,b);
cout<<n<<"\n";
for(int i = 1; i <= n; i ++)
{
s[i].a.wt();
s[i].b.wt();
printf("%.5lf\n",sqrt(chang(s[i].a - s[i].b)));
}
}
return 0;
}
```