UVA Solution 453 – Intersecting Circles – Volume 4

UVA Solution 453 – Intersecting Circles – Volume 4

UVA Online Judge Solution 453 – Intersecting Circles | Volume 4
UVA Problem Link –

Problem Name: 453 – Intersecting Circles solution
Problem Number : UVA – 453 – Intersecting Circles solution
Online Judge : UVA Online Judge Solution
Volume: 4
Solution Language : C plus plus

UVA Solution 453 – Intersecting Circles Code in CPP:

#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;
}

Tags: UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list, UVA 453  code in C, UVA code in C++, UVA 453 solution in C, UVA Intersecting Circles solution