Problem: Find common tangent lines of two circles $c1$ and $c2$.

Constraints

* $-1,000 \leq c1x, c1y, c2x, c2y \leq 1,000$
* $1 \leq c1r, c2r \leq 1,000$
* $c1$ and $c2$ are different

Input

Center coordinates ($cix$, $ciy$) and radii $cir$ of two circles $c1$ are $c2$ are given in the following format.

$c1x \; c1y \; c1r$
$c2x \; c2y \; c2r$

All input values are given in integers.

Output

Print coordinates of the tangent points on circle $c1$ based on the following rules.

* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

1 1 1
6 2 2


Output

0.6153846154 1.9230769231
1.0000000000 0.0000000000
1.4183420913 1.9082895434
1.7355040625 0.3224796874


Input

1 2 1
4 2 2


Output

0.6666666667 1.0571909584
0.6666666667 2.9428090416
2.0000000000 2.0000000000


Input

1 2 1
3 2 2


Output

0.5000000000 1.1339745962
0.5000000000 2.8660254038


Input

0 0 1
1 0 2


Output

-1.0000000000 0.0000000000


Input

0 0 1
0 0 2


Output

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
typedef double db;
const db eps = 1e-8;
const db inf = 1e20;
const db pi = acos(-1.0);
const int maxp = 1010;
// Compares a double to zero
int sgn(db x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}
//square of a double 
inline db sqr(db x){return x*x;}

struct Point{
    db x, y;
    Point(){}
    Point(db x, db y):x(x), y(y){}
    void input(){
        //如果为longdouble则需要改为Lf
        scanf("%lf%lf",&x, &y);
    }
    void output(){
        printf("%.2f %.2f\n", x,y);
    }
    bool operator == (Point b)const {
        return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    Point operator - (const Point &b)const{
        return Point(x - b.x, y - b.y);
    }
    //叉积
    db operator ^ (const Point &b)const{
        return x * b.y - y * b.x;
    }
    //点积
    db operator * (const Point &b)const{
        return x * b.x + y * b.y;
    }
    // 返回长度
    db len(){
        return hypot(x, y);
    } 
    // 返回长度平方
    db len2(){
        return x * x + y * y;
    }
    //返回两点距离 
    db distance(Point p){
        return hypot(x - p.x, y - p.y);
    }
    Point operator + (const Point &b)const{
        return Point(x + b.x, y + b.y);
    }
    Point operator * (const db &k) const {
        return Point(x * k,  y * k);
    }
    Point operator /(const db &k)const {
        return Point(x / k, y / k);
    }
    // 计算 pa 和 pb 的夹角
    // 就是求这个点看 a，b所成的夹角
    // LightOJ 1203
    db rad(Point a, Point b){
        Point p = *this;
        return fabs(atan2( fabs((a-p)^(b-p)), (a-p) * (b-p) ));
    }
    // 化为长度为 r 的向量
    Point trunc(db r){
        db l = len();
        if(!sgn(l)) return *this;
        r /= l;
        return Point(x*r, y*r);
    }
    // 逆时针旋转90度
    Point rotleft(){
        return Point(-y, x);
    }
    // 顺时针转90度
    Point rotright(){
        return Point(y, -x);
    }
    //绕点 p 逆时针旋转 angle
    Point rotate(Point p, db angle){
        Point v = (*this) - p;
        db c = cos(angle), s = sin(angle);
        return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
    }
};


struct Line{
    Point s, e;
    Line(){}
    Line(Point s, Point e):s(s),e(e){}
    bool operator == (Line v){
        return (s == v.s) && (e == v.e);
    }
    // 根据一个点和倾斜角angle确定直线， 0 <= angle < pi
    Line (Point p, db angle){
        s = p;
        if(sgn(angle - pi / 2) == 0){
            e = (s + Point(0, 1));
        }else{
            e = (s + Point(1, tan(angle)));
        }
    }

    // ax + by + c = 0
    Line (db a, db b, db c){
        if(sgn(a) == 0){ //  y = -c / b
            s = Point(0, -c/b);
            e = Point(1, -c/b);
        } else if (sgn(b) == 0){ // x = -c / a
            s = Point(-c/a, 0);
            e = Point(-c/a, 1);
        }else{//(0, -c/b), (1, (-c-a)/b)
            s = Point(0, -c/b);
            e = Point(1, (-c-a)/b);
        }
    }

    void input(){
        s.input();
        e.input();
    }
    void adjust(){
        if(e < s) swap(s, e);
    }
    db length(){
        return s.distance(e);
    }
    // 返回直线倾斜角 0 <= angle < pi
    db angle(){
        db k = atan2(e.y - s.y, e.x - s.x);
        if(sgn(k) < 0) k += pi;
        if(sgn(k - pi) == 0) k -= pi;
        return k;
    }
    /*
        点和直线的关系
        1 在左侧
        2 在右侧
        3 在直线上
    */
    int relation(Point p){
        int c = sgn((p-s) ^ (e-s));
        if(c < 0) return 1;
        else if(c > 0) return 2;
        else return 3;
    }
    // 点在线段上的判断，包括端点
    bool pointonseg(Point p){
        return sgn((p-s)^(e-s)) == 0 && sgn((p-s) * (p-e)) <= 0;
    }
    // 两向量平行（对应直线平行或重合）
    bool parallel(Line v){
        return sgn((e - s) ^ (v.e - v.s)) == 0;
    }
    /*
        两线段相交判断
        2 规范相交
        1 非规范相交
        0 不相交
    */

    int segcrosseg(Line v){
        int d1 = sgn((e - s) ^ (v.s - s));  //v.s 在 线段的哪一侧
        int d2 = sgn((e - s) ^ (v.e - s));  //v.e 在 线段的哪一侧
        int d3 = sgn((v.e - v.s) ^ (s - v.s));  
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if((d1^d2) == -2 && (d3^d4) == -2) return 2; // 跨立实验满足 一个是-1一个是1

        // 1. v.s在线段上 || v.e 在线段上 || s 在另外一条线段上 || e在另外一条线段上
        return (d1 == 0 &&  sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) || 
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }
    /*
        直线与线段相交判断
        *this line -v seg 
        2 规范相交
        1 非规范相交
        0 不相交
    */
    int linecorssseg(Line v){ // v是线段
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        if((d1 ^ d2) == -2) return 2;
        return (d1 == 0 || d2 == 0);
    }
    /*
        两直线关系
        0 平行
        1 重合
        2 相交
    */
    int linecrossline(Line v){
        // 如果平行，则看点是否在直线上
        if((*this).parallel(v)) return v.relation(s) == 3;
        return 2;
    }

    /*
        求两直线的交点
        要保证两直线不平行或重合
    */
    Point crosspoint(Line v){
        db a1 = (v.e - v.s) ^ (s - v.s);
        db a2 = (v.e - v.s) ^ (e - v.s);
        return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
    }

    // 点到直线的距离
    db dispointtoline(Point p){
        return fabs((p-s) ^ (e-s)) / length();
    }

    // 点到线段的距离
    db dispointtoseg(Point p){
        if(sgn((p-s)*(e-s)) < 0 || sgn((p-e) * (s-e)) < 0)
            return min(p.distance(s), p.distance(e));
        return dispointtoline(p);
    } 
    /*
        返回线段到线段的距离
        前提是两线段不相交，相交距离就是 0 了
    */
    db dissegtoseg(Line v){
        return min(min(dispointtoseg(v.s), dispointtoseg(v.e)), min(v.dispointtoseg(s), v.dispointtoseg(e)));
    }

    /*
        返回 p 在直线上的投影
    */
    Point lineprog(Point p){
        return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
    }
    // 返回点 p 关于直线的对称点
    Point symmetrypoint(Point p){
        Point q = lineprog(p);
        return Point(2*q.x - p.x, 2 * q.y - p.y);
    }
};

struct circle{
    Point p;
    db r;
    circle(){}
    circle(Point p, db r):p(p), r(r){}
    void input(){
        p.input();
        // 注意类型
        scanf("%lf", &r);
    }
    circle(db x, db y, db r){
        p = Point(x, y);
        this->r = r;
    }
    /*
        三角形的外接圆
        需要Point 的 + / rotate() 以及 Line 的crosspoint()
        利用两条边的中垂线得到圆心
        UVA 12304
    */
    circle(Point a, Point b, Point c){
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
        p = u.crosspoint(v);
        r = p.distance(a);
    }
    /*
        三角形的内切圆
        bool t 没有作用，只是为了和上面外接圆函数区别
        UVA 12304
    */
    circle(Point a, Point b, Point c, bool t){
        Line u, v;
        // u 为角 a 的平分线
        db m  = atan2(b.y-a.y, b.x-a.x), n = atan2(c.y - a.y, c.x - a.x);
        u.s = a;
        u.e = u.s + Point(cos((n+m)/2), sin((n+m)/2));
        // v 为角 b 的平分线
        m = atan2(a.y-b.y, a.x-b.x), n = atan2(c.y-b.y, c.x-b.x);
        v.s = b;
        v.e = v.s + Point(cos((n+m)/2), sin((n+m)/2));
        p = u.crosspoint(v);
        r = Line(a,b).dispointtoseg(p);
    }
    // 通过圆心角确定圆上的一个点
    Point point(db a){
        return Point(p.x + cos(a) * r, p.y + sin(a) * r);
    }
    bool operator == (circle v){
        return (p == v.p) && sgn(r - v.r) == 0;
    }
    bool operator < (circle v)const{
        return ((p<v.p) || (p == v.p) && sgn(r - v.r) < 0);
    }
    // 面积
    db area(){
        return pi * r * r;
    }
    // 周长
    db circumference(){
        return 2 * pi * r;
    }
    /*
        点和圆的关系
        0 圆外
        1 圆上
        2 圆内
    */
   int relation(Point b){
       db dst = b.distance(p);
       if(sgn(dst - r) < 0) return 2;
       else if(sgn(dst - r) == 0) return 1;
       return 0;
   }
   /*
        线段和圆的关系
        比较的是圆心到线段的距离和半径的关系
        2 交
        1 切
        0 不交
   */
    int relation(Line v){
        db dst = v.dispointtoseg(p);
        if(sgn(dst - r) < 0) return 2;
        else if(sgn(dst - r) == 0) return 1;
        return 0;
    }
    int relationline(Line v){
        db dst = v.dispointtoline(p);
        if(sgn(dst - r) < 0) return 2;
        else if(sgn(dst - r) == 0) return 1;
        return 0;
    }
    /*
        两圆的关系
        5 相离
        4 外切
        3 相交
        2 内切
        1 内含
    */
    int relationcircle(circle v){
        db d = p.distance(v.p);
        if(sgn(d - r - v.r) > 0) return 5;
        if(sgn(d - r - v.r) == 0) return 4;
        db l = fabs(r - v.r);
        if(sgn(d - r - v.r) < 0 && sgn(d - l) > 0) return 3;
        if(sgn(d - l) == 0) return 2;
        if(sgn(d - l) < 0) return 1;
    }
    /*
        求两个圆的交点，返回0表示没有交点，返回1是一个交点，2是两个交点
    */
    int pointcrosscircle(circle v, Point &p1, Point &p2){
        int rel = relationcircle(v);
        if(rel == 1 || rel == 5) return 0;
        db d = p.distance(v.p);
        db l = (d * d + r * r - v.r * v.r) / (2 * d);
        db h = sqrt(r * r - l * l);
        Point tmp = p + (v.p - p).trunc(l);
        p1 = tmp + ((v.p - p).rotleft().trunc(h));
        p2 = tmp + ((v.p - p).rotright().trunc(h));
        if(rel == 2 || rel == 4)return 1;
        return 2;
    }
    // 求直线与圆的交点，返回交点个数
    int pointcrossline(Line v, Point &p1, Point &p2){
        if(!(*this).relationline(v)) return 0;
        Point a = v.lineprog(p);
        db d = v.dispointtoline(p);
        d = sqrt(r * r - d * d);
        if(sgn(d) == 0){
            p1 = a;
            p2 = a;
            return 1;
        }
        p1 = a + (v.e - v.s).trunc(d);
        p2 = a - (v.e - v.s).trunc(d);
        return 2;
    }
    // 得到 a，b两点，半径为r1的两个圆
    int getcircle(Point a, Point b, db r1, circle &c1, circle &c2){
        circle x(a, r1), y(b, r1);
        int t = x.pointcrosscircle(y, c1.p, c2.p);
        if(!t) return 0;
        c1.r = c2.r = r;
        return t;
    }
    // 得到与直线 u 相切，过点 q， 半径为 r1 的圆
    int getcircle(Line u, Point q, db r1, circle &c1, circle &c2){
        db dis = u.dispointtoline(q);
        if(sgn(dis - r1 * 2) > 0) return 0;
        if(sgn(dis) == 0){
            c1.p = q + ((u.e - u.s).rotleft().trunc(r1));
            c2.p = q + ((u.e - u.s).rotright().trunc(r1));
            c1.r = c2.r = r1;
            return 2;
        }
        Line u1 = Line((u.s + (u.e - u.s).rotleft().trunc(r1)), (u.e + (u.e - u.s).rotleft().trunc(r1)));
        Line u2 = Line((u.s + (u.e - u.s).rotright().trunc(r1)), (u.e + (u.e - u.s).rotright().trunc(r1)));
        circle cc = circle(q, r1);
        Point p1, p2;
        if(!cc.pointcrossline(u1, p1, p2)) cc.pointcrossline(u2, p1, p2);
        c1 = circle(p1, r1);
        if(p1 == p2){
            c2 = c1;
            return 1;
        }
        c2 = circle(p2, r1);
        return 2;
    }
    // 同时与直线u，v相切，半径为r1的圆 
    int getcircle(Line u, Line v, db r1, circle &c1, circle &c2, circle &c3, circle &c4){
        if(u.parallel(v)) return 0;
        Line u1 = Line(u.s + (u.e - u.s).rotleft().trunc(r1), u.e + (u.e - u.s).rotleft().trunc(r1));
        Line u2 = Line(u.s + (u.e - u.s).rotright().trunc(r1), u.e + (u.e - u.s).rotright().trunc(r1));
        Line v1 = Line(v.s + (v.e - v.s).rotleft().trunc(r1), v.e + (v.e - v.s).rotright().trunc(r1));
        Line v2 = Line(v.s + (v.e - v.s).rotleft().trunc(r1), v.e + (v.e - v.s).rotright().trunc(r1));
        
        c1.r = c2.r = c3.r = c4.r = r1;
        c1.p = u1.crosspoint(v1);
        c2.p = u1.crosspoint(v2);
        c3.p = u2.crosspoint(v1);
        c4.p = u2.crosspoint(v2);
        return 4;
    }
    // 同时与不相交圆 cx, cy 相切，半径为r1的圆
    int getcircle(circle cx, circle cy, db r1, circle &c1, circle &c2){
        circle x(cx.p, r1+cx.r), y(cy.p, r1+cy.r);
        int t = x.pointcrosscircle(y, c1.p, c2.p);
        if(!t) return 0;
        c1.r = c2.r = r1;
        return t;
    }
    // 过一点作圆的切线 (先判断点和圆的关系)
    int tangentline(Point q, Line &u, Line &v){
        int x = relation(q);
        if(x == 2) return 0; //圆内
        if(x == 1){ //圆上
            u = Line(q, q+(q-p).rotleft());
            v = u;
            return 1;
        }
        db d = p.distance(q);
        db l = r * r / d;
        db h = sqrt(r * r - l * l);
        u = Line(q, p + ((q - p).trunc(l) + (q-p).rotleft().trunc(h)));
        v = Line(q, p + (q - p).trunc(l) + (q - p).rotright().trunc(h));
        return 2;
    }
    // 求两圆相交的面积
    db areacircle(circle v){
        int rel = relationcircle(v);
        if(rel >= 4) return 0.0;
        if(rel <= 2) return min(area(), v.area()); //内部
        db d = p.distance(v.p);
        db hf = (r + v.r + d) / 2.0;
        db ss = 2 * sqrt(hf*(hf - r) * (hf - v.r) * (hf - d));
        db a1 = acos((r * r + d * d - v.r * v.r) / (2.0 * r * d));
        a1 = a1 * r * r;
        db a2 = acos((v.r * v.r + d * d - r * r) / (2.0 * v.r * d));
        a2 = a2 * v.r * v.r;
        return a1 + a2 - ss;
    }
    // 求圆和三角形 pab 的相交面积
    // POJ3675 HDU3982 HDU2892
    db areatriangle(Point a, Point b){
        if(sgn((p-a)^(p-b)) == 0)return 0.0;
        Point q[5];
        int len = 0;
        q[len++] = a;
        Line l(a, b);
        Point p1, p2;
        if(pointcrossline(l, q[1], q[2]) == 2){
            if(sgn((a-q[1]) * (b-q[1])) < 0) q[len++] = q[1];
            if(sgn((a-q[2]) * (b-q[2])) < 0) q[len++] = q[2];
        }
        q[len++] = b;
        if(len == 4 && sgn((q[0] - q[1]) * (q[2] - q[1])) > 0) swap(q[1], q[2]);
        db res = 0;
        for(int i=0;i<len-1;i++){
            if(relation(q[i]) == 0 || relation(q[i+1]) == 0){
                db arg = p.rad(q[i], q[i+1]);
                res += r * r * arg / 2.0;
            }else{
                res += fabs((q[i] - p) ^ (q[i+1] - p)) / 2.0;
            }
        }
        return res;
    }
};
typedef Point Vector;
// 求两个圆的公切线
int getTangents(circle A, circle B, Point*a, Point *b){
    int cnt = 0;
    if(A.r < B.r) return getTangents(B, A, b, a);
    int d2 = (A.p-B.p).len2();// 圆心距平方
    int rdiff = A.r - B.r;
    int rsum = A.r + B.r;
    if(d2 < rdiff * rdiff) return 0; // 包含,没有公切线
    Vector AB = B.p - A.p;
    db base = atan2(AB.y, AB.x);
    if(d2 == 0 && A.r == B.r) return -1;// 无限多切线
    if(d2 == rdiff * rdiff){ // 内切
        a[cnt] = A.point(base);
        b[cnt] = B.point(base);cnt++;
        return 1;
    }

    // 有外公切线
    db 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(d2 == rsum * rsum){
        a[cnt] = A.point(base); b[cnt] = B.point(pi+base); cnt++;
    }
    else if(d2 > rsum * rsum){
        db 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;
}
Point a[10], b[10];
int main(){
    circle c1, c2;
    c1.input();
    c2.input();
    int cnt = getTangents(c1, c2, a, b);
    sort(a, a + cnt);
    for(int i=0;i<cnt;i++){
        printf("%.8f %.8f\n", a[i].x , a[i].y);
    }
    return 0;
}