Intersecting Circles

The equation of a circle with radius r and center is

Write a program that compares two circles to see if they intersect and, if they do, computes the points of intersection. (There can be 1, 2, or and infinite number of such points).

Input

The input to this program will consist of a pair number of lines. Each two lines represent a intersection problem. Each line will contain 3 real numbers constituting the , and r parameters for one circle.

Output

For each problem, the output should be the words "NO INTERSECTION" if the circles do not intersect.

When they have an infinite number of intersection points, the output should be the words "THE CIRCLES ARE THE SAME"

If they do intersect at 1 or 2 points, the output should be a line with one or two pairs, respectively, of real numbers giving the x and y coordinates of any point of intersection. Pairs must be sorted first by their x coordinate and when these are equal by the y coordinate.

Each pair is to be printed in parenthesis with numbers accurately rounded to three digits to the right of the decimal point, as the sample below.

Sample Input

0.0 0.0 1.0
3.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
1.0 0.0 1.0

Sample Output

NO INTERSECTION
THE CIRCLES ARE THE SAME
(0.500,-0.866)(0.500,0.866)

---

簡單說明一下做法，

拉連心線，兩圓心距離，然後分成幾種可能。

如果 disAB, A.r, B.r 構不成三角形則沒相交//外離或內離

交一點的時候討論// 內切或外切

交兩點的時候，使用旋轉向量求交點。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Cir {
    double x, y, r;
    int scan() {
        return scanf("%lf %lf %lf", &x, &y, &r) == 3;
    }
};
#define eps 1e-6
struct Pt {
    double x, y;
    bool operator<(const Pt other) const {
        if(fabs(x-other.x) < eps)
            return y < other.y;
        return x < other.x;
    }
};
int IntersectCir(Cir A, Cir B, Pt v[]) { // Pt v[] result buffer
    double disAB = sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    if(fabs(disAB) < eps && fabs(A.r-B.r) < eps) {
        if(A.r < eps) {
            v[0].x = A.x;
            v[0].y = A.y;
            return 1;
        }
        return 0;
    }
    if(A.r+B.r+eps < disAB || A.r+disAB+eps < B.r || B.r+disAB+eps < A.r) {
        return -1;
    }
    double x, y, vx, vy;
    vx = B.x - A.x;
    vy = B.y - A.y;
    if(fabs(disAB-A.r-B.r) < eps || fabs(A.r-disAB-B.r) < eps ||
       fabs(B.r-A.r-disAB) < eps) {
        if(fabs(disAB-A.r-B.r) < eps) { // (A)(B)
            v[0].x = A.x+vx*A.r/(A.r+B.r);
            v[0].y = A.y+vy*A.r/(A.r+B.r);
        } else {
            if(A.r < B.r) { //((A)B)
                v[0].x = A.x-vx*A.r/(B.r-A.r);
                v[0].y = A.y-vy*A.r/(B.r-A.r);
            } else { //((B)A)
                v[0].x = B.x+vx*B.r/(A.r-B.r);
                v[0].y = B.y+vy*B.r/(A.r-B.r);
            }
        }
        return 1;
    }
    double theta = acos((A.r*A.r+disAB*disAB-B.r*B.r)/2/A.r/disAB);
    double rvx, rvy; //rotate vector
    rvx = vx*cos(theta)-vy*sin(theta);
    rvy = vx*sin(theta)+vy*cos(theta);
    v[0].x = A.x+rvx*A.r/disAB;
    v[0].y = A.y+rvy*A.r/disAB;
    rvx = vx*cos(-theta)-vy*sin(-theta);
    rvy = vx*sin(-theta)+vy*cos(-theta);
    v[1].x = A.x+rvx*A.r/disAB;
    v[1].y = A.y+rvy*A.r/disAB;
    return 2;
}
int main() {
    Cir A, B;
#define eps2 5.14e-5
    while(A.scan()) {
        B.scan();
        Pt p[2];
        int r = IntersectCir(A, B, p);
        if(r == 0)
            puts("THE CIRCLES ARE THE SAME");
        else if(r < 0)
            puts("NO INTERSECTION");
        else if(r == 1)
            printf("(%.3lf,%.3lf)\n", p[0].x+eps2, p[0].y+eps2);
        else {
            sort(p, p+2);
            printf("(%.3lf,%.3lf)(%.3lf,%.3lf)\n", p[0].x+eps2, p[0].y+eps2, p[1].x+eps2, p[1].y+eps2);
        }
    }
    return 0;
}