计算几何 - Tangents - UVA 10674

计算几何 - Tangents - UVA 10674

题意：

给 顶 两 个 圆 的 圆 心 ， 半 径 ， 求 出 这 两 个 圆 的 所 有 公 切 线 。 给顶两个圆的圆心，半径，求出这两个圆的所有公切线。 给顶两个圆的圆心，半径，求出这两个圆的所有公切线。

输入：

多 组 测 试 数 据 ， 多组测试数据， 多组测试数据，

六 个 整 数 ， x 1 , y 1 , r 1 , x 2 , y 2 , r 2 ， 分 别 表 示 第 一 个 圆 和 第 二 个 圆 的 横 、 纵 坐 标 ， 半 径 。 六个整数，x_1,y_1,r_1,x_2,y_2,r_2，分别表示第一个圆和第二个圆的横、纵坐标，半径。 六个整数，x1​,y1​,r1​,x2​,y2​,r2​，分别表示第一个圆和第二个圆的横、纵坐标，半径。

输出：

首 行 一 个 整 数 ， 表 示 切 线 的 条 数 。 首行一个整数，表示切线的条数。 首行一个整数，表示切线的条数。

若 有 无 数 条 切 线 ( 两 圆 重 合 ) ， 输 出 − 1 。 若有无数条切线(两圆重合)，输出-1。 若有无数条切线(两圆重合)，输出−1。

五 个 浮 点 数 S x , S y , T x , T y , L ， 分 别 表 示 切 线 在 第 一 个 圆 上 和 第 二 个 圆 上 的 切 点 的 横 纵 坐 标 ， 最 后 一 个 数 表 示 切 线 长 。 五个浮点数S_x,S_y,T_x,T_y,L，分别表示切线在第一个圆上和第二个圆上的切点的横纵坐标，\\最后一个数表示切线长。 五个浮点数Sx​,Sy​,Tx​,Ty​,L，分别表示切线在第一个圆上和第二个圆上的切点的横纵坐标，最后一个数表示切线长。

以 S x 为 第 一 关 键 字 ， S y 为 第 二 关 键 字 ， 将 结 果 升 序 排 序 后 输 出 。 以S_x为第一关键字，S_y为第二关键字，将结果升序排序后输出。 以Sx​为第一关键字，Sy​为第二关键字，将结果升序排序后输出。

Sample Input

10 10 5 20 20 5
10 10 10 20 20 10
10 10 5 20 10 5
0 0 0 0 0 0

Sample Output

4
6.46447 13.53553 16.46447 23.53553 14.14214
10.00000 15.00000 20.00000 15.00000 10.00000
13.53553 6.46447 23.53553 16.46447 14.14214
15.00000 10.00000 15.00000 20.00000 10.00000
2
2.92893 17.07107 12.92893 27.07107 14.14214
17.07107 2.92893 27.07107 12.92893 14.14214
3
10.00000 5.00000 20.00000 5.00000 10.00000
10.00000 15.00000 20.00000 15.00000 10.00000
15.00000 10.00000 15.00000 10.00000 0.00000

数据范围：

− 100 ≤ x 1 , y 1 , x 2 , y 2 ≤ 100 , 0 < r 1 , r 2 ≤ 200. −100 ≤ x_1,y_1,x_2,y_2 ≤ 100, 0 < r_1,r_2≤ 200. −100≤x1​,y1​,x2​,y2​≤100,0<r1​,r2​≤200.

---

注意：

题 中 虽 然 说 输 入 的 都 是 整 数 ， 但 是 还 是 要 以 浮 点 数 的 形 式 读 入 ， 否 则 就 会 疯 狂 W A ( 为 什 么 ？ ？ ？ ？ ) 题中虽然说输入的都是整数，但是还是要以浮点数的形式读入，否则就会疯狂WA(为什么？？？？) 题中虽然说输入的都是整数，但是还是要以浮点数的形式读入，否则就会疯狂WA(为什么？？？？)

为 了 输 出 ， 可 以 写 一 个 点 对 结 构 体 重 载 一 下 小 于 号 。 为了输出，可以写一个点对结构体重载一下小于号。 为了输出，可以写一个点对结构体重载一下小于号。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const double eps=1e-10;
const double pi=acos(-1.0);

struct Point 
{
    double x,y;
    int id;
    Point(double x=0,double y=0) : x(x), y(y) {}
};

//点与向量
typedef Point Vector;

Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }

Vector operator - (Point A,Point B) { return Vector(A.x-B.x,A.y-B.y); }

Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }

Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }

int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0 ? -1 : 1;
}

bool operator < (const Point &a,const Point &b)
{
    return a.x<b.x || (!dcmp(a.x-b.x) && a.y<b.y);
}

bool operator == (const Point &a, const Point &b)
{
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}

double Dot(Vector A,Vector B) { return A.x*B.x + A.y*B.y; }

double Length(Vector A) { return sqrt(Dot(A,A)); }

double Angle(Vector A, Vector B) { return acos(Dot(A,B) / Length(A) / Length(B)); } //A和B夹角

double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }  //若A到B逆时针则为正，否则为负

double Area2(Point A,Point B,Point C) { return Cross(B-A,C-A); }    //三角形ABC的面积的两倍(有方向)

double angle(Vector v) { return atan2(v.y,v.x); }   //arctan(y/x)

double dis2(Point A,Point B) { return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y); }

//圆
struct Circle
{
    Point c;
    double r;
    Circle(Point c, double r):c(c), r(r) {}
    Point point(double a)
    {//通过圆心角求坐标
        return Point(c.x + cos(a)*r, c.y + sin(a)*r);
    }
}; 

//求两圆的公切线
//返回切线的条数，-1表示无穷条切线(两圆重合)
// a[i]和b[i]分别表示第i条切线在圆A和圆B上的切点
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=dis2(A.c,B.c);
    double rdiff=A.r-B.r;
    double rsum=A.r+B.r;
    if(d2<rdiff*rdiff) return 0;    //内含
    
    double base=atan2(B.c.y-A.c.y,B.c.x-A.c.x);
    if(!dcmp(d2) && !dcmp(A.r-B.r)) return -1;    //重合
    if(!dcmp(d2-rdiff*rdiff))     //内切，1条切线
    {
        a[cnt]=A.point(base); b[cnt]=B.point(base); cnt++;
        return 1;
    }
    //有外公切线
    double ang=acos((A.r-B.r)/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))
    {
        a[cnt]=A.point(base); 
        b[cnt]=B.point(pi+base); 
        cnt++;
    }
    else if(d2>rsum*rsum)
    {
        double ang=acos((A.r+B.r)/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;
}

struct Point_pair
{
    Point A,B;
    bool operator < (const Point_pair &t) const
    {
        if(dcmp(t.A.x-A.x)==0) return A.y<t.A.y;
        return A.x<t.A.x;
    }
};

int main()
{
    double a,b,r1,c,d,r2;
    while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&r1,&c,&d,&r2))
    {
        if(!dcmp(a)&&!dcmp(b)&&!dcmp(r1)&&!dcmp(c)&&!dcmp(d)&&!dcmp(r2)) break;
        Point O1=Point(a,b), O2=Point(c,d);
        Circle A=Circle(O1,r1), B=Circle(O2,r2);
        Point u[20], v[20];
        Point_pair p[20];
        int t=getTangents(A,B,u,v);
        for(int i=0;i<t;i++) p[i].A=u[i], p[i].B=v[i];
        if(t>0) sort(p,p+t);
        
        printf("%d\n",t);
        for(int i=0;i<t;i++) printf("%.5lf %.5lf %.5lf %.5lf %.5lf\n",
                                p[i].A.x,p[i].A.y,p[i].B.x,p[i].B.y,Length(p[i].A-p[i].B));
    }
    return 0;
}