mmd 和 cz 的智慧结晶。某次比赛的时候写的。
/**//*
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;
}