两圆求交点

/**//*

1: 两个圆相离

2:两个圆外切

3:两个圆内切

4:两个圆相交

5:如果两个圆相含(包括两圆坐标和半径都相同)

*/

int circle_intersect(circle_t A, circle_t B, point_t &ia, point_t &ib)

{

   if (A.x == B.x && A.y == B.y)

       return 5;

   double dd = dist (A.x, A.y, B.x, B.y);

   if (A.r + B.r + EP < dd)

       return 1;

   

   double k, a, b, d, aa, bb, cc, c, drt;

   k = A.r;

   a = B.x - A.x;

   b = B.y - A.y;

   c = B.r;

   d = sqr(c) - sqr(k) - sqr(a) - sqr(b);

   

   aa = 4 * sqr(a) + 4 * sqr(b);

   bb = 4 * b * d;

   cc = sqr(d) - 4 * sqr(a) * sqr(k);

   

   drt = sqr(bb) - 4 * aa * cc;

   if (drt < 0)

       return 5;

   drt = sqrt (drt);

   ia.y = (-bb + drt) / 2 / aa;

   ib.y = (-bb - drt) / 2 / aa;

   if (abs (a) < EP)

   {

       ia.x = sqrt (sqr (k) - sqr (ia.y));

       ib.x = -ia.x;

   }

   else

   {

       ia.x = (2 * b * ia.y + d) / -2 / a;

       ib.x = (2 * b * ib.y + d) / -2 / a;

   }

   ia.x += A.x;

   ia.y += A.y;

   ib.x += A.x;

   ib.y += A.y;

   if (abs (ia.y - ib.y) < EP)

   {

       if (abs (A.r + B.r - dd) < EP)

           return 2;

       if (abs (dd - (max (A.r, B.r) - min (A.r, B.r))) < EP)

           return 3;

   }

   return 4;

}