题意:
给出两个圆的圆心坐标和半径，求这两个圆的公切线切点的坐标及对应线段长度。若两圆重合，有无数条公切线则输出-1.
输出是按照一定顺序输出的。
分析：
首先情况比较多，要一一判断，不要漏掉。
如果高中的那点老底还在的话，代码还是很好理解的。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const double PI = acos(-1.0);
const double EPS = 1e-;
struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y) {} };
typedef Point Vector;
Vector operator + (Vector A, Vector B)
{
return Vector(A.x+B.x, A.y+B.y);
}
Vector operator - (Vector A, Vector B)
{
return Vector(A.x-B.x, A.y-B.y);
}
Vector operator * (Vector A, double p)
{
return Vector(A.x*p, A.y*p);
}
Vector operator / (Vector A, double p)
{
return Vector(A.x/p, A.y/p);
}
double dcmp(double x)
{
if(fabs(x) < EPS) return ;
else return x < ? - : ;
}
bool operator < (const Vector& a, const Vector& b)
{
return dcmp(a.x-b.x) < || dcmp(a.x-b.x) == && dcmp(a.y-b.y) < ;
}
bool operator == (const Vector& a, const Vector& b)
{
return dcmp(a.x-b.x) == && dcmp(a.y-b.y) == ;
}
double Dot(Vector a, Vector b)
{
return a.x*b.x + a.y*b.y;
}
double Cross(Vector a, Vector b)
{
return a.x*b.y - a.y*b.x;
}
double Length(Vector a)
{
return sqrt(Dot(a, a));
}
struct Circle
{
double x, y, r;
Circle(double x, double y, double r):x(x), y(y), r(r) {}
Point point(double a)
{
return Point(x + r*cos(a), y + r*sin(a));
}
};
int getTangents(Circle A, Circle B, Point* a, Point* b)
{
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
double d2 = (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
double rdiff = A.r - B.r;
double rsum = A.r + B.r;
if(d2 < rdiff*rdiff) return ; //内含 double base = atan2(B.y-A.y, B.x-A.x);
if(dcmp(d2) == && dcmp(A.r - B.r) == ) return -; //重合
if(dcmp(d2 - rdiff*rdiff) == ) //内切
{
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
} //有外公切线
double 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(dcmp(rsum*rsum - d2) == )
{//外切
a[cnt] = b[cnt] = A.point(base); cnt++;
}
else if(dcmp(d2 - rsum*rsum) > )
{
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;
} int main(void)
{
#ifdef LOCAL
freopen("10674in.txt", "r", stdin);
#endif int x1, y1, r1, x2, y2, r2;
while(scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2) == && r1 && r2)
{
Point a[], b[];
Circle C1(x1, y1, r1), C2(x2, y2, r2);
int n = getTangents(C1, C2, a, b);
printf("%d\n", n);
int p[] = {, , , };
for(int i = ; i < n; ++i)
for(int j = i+; j < n; ++j)
if(a[p[j]] < a[p[i]] || (a[p[j]] == a[p[i]] && b[p[j]] < b[p[i]])) swap(p[i], p[j]);
for(int i = ; i < n; ++i)
printf("%.5lf %.5lf %.5lf %.5lf %.5lf\n", a[p[i]].x, a[p[i]].y, b[p[i]].x, b[p[i]].y, Length(a[p[i]] - b[p[i]]));
} return ;
}
代码君
写的第一份，样例过，自己随机生成的1000组数据和lrj的代码对比，输出也是一模一样的，可就是无线WA。
这里还是贴一下这份“神奇”的代码吧，也许日后能发现这个隐藏的错误。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std; struct Point
{
double x, y;
Point(double x=, double y=) :x(x),y(y) {}
};
typedef Point Vector;
const double EPS = 1e-;
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }
bool operator < (const Point& a, const Point& b)
{ return a.x < b.x || (a.x == b.x && a.y < b.y); }
int dcmp(double x)
{ if(fabs(x) < EPS) return ; else return x < ? - : ; }
bool operator == (const Point& a, const Point& b)
{ return dcmp(a.x-b.x) == && dcmp(a.y-b.y) == ; }
double Dot(Vector A, Vector B)
{ return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); } struct Circle
{
Point c; //Ô²ÐÄ
double r; //°ë¾¶
//Circle(Point c, double r):c(c), r(r) {}
Point point(double a)
{//Çó¶ÔÓ¦Ô²ÐĽǵĵã
return Point(c.x + r*cos(a), c.y + r*sin(a));
}
};
double angle(Vector v) { return atan2(v.y, v.x); }
const double PI = acos(-1.0); int getTangents(Circle A, Circle B, Point* a, Point* b)
{
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
double d2 = (A.c.x-B.c.x)*(A.c.x-B.c.x) + (A.c.y-B.c.y)*(A.c.y-B.c.y);
double rdiff = A.r - B.r;
double rsum = A.r + B.r;
if(d2 < rdiff*rdiff) return ; //ÄÚº¬ double base = atan2(B.c.y-A.c.y, B.c.x-A.c.x);
if(dcmp(d2) == && dcmp(A.r-B.r) == ) return -; //Á½Ô²Öغϣ¬ÎÞÇî¶àÌõÇÐÏß
if(dcmp(d2 - rdiff*rdiff) == ) //ÄÚÇÐ
{
a[cnt] = A.point(base);
b[cnt] = B.point(base);
cnt++;
return ;
}
//ÓÐÍ⹫ÇÐÏß
double 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(dcmp(d2 - rsum*rsum) == ) //Ò»ÌõÄÚ¹«ÇÐÏß
{
a[cnt] = b[cnt] = A.point(base); cnt++;
}
else if(dcmp(d2 - rsum*rsum) > )
{
double ang = acos((A.r+B.r) / sqrt(d2));
a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang+PI); cnt++;
a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang+PI); cnt++;
}
//for(int i = 0; i < cnt; ++i)
// printf("%.5lf %.5lf %.5lf %.5lf\n", a[i].x, a[i].y, b[i].x, b[i].y);
return cnt;
} int main(void)
{
#ifdef LOCAL
freopen("10674in.txt", "r", stdin);
//freopen("10674out.txt", "w", stdout);
#endif int x1, y1, r1, x2, y2, r2;
while(scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2) == && dcmp(r1) > )
{
Point a[], b[];
/*Point p1(x1, y1), p2(x2, y2);
Circle C1(p1, r1), C2(p2, r2);*/
Circle C1, C2;
C1.c.x=x1, C1.c.y=y1, C1.r=r1;
C2.c.x=x2, C2.c.y=y2, C2.r=r2;
int n = getTangents(C1, C2, a, b);
printf("%d\n", n);
if(n > )
{
int p[] = {, , , };
for(int i = ; i < n; ++i)
for(int j = i+; j < n; ++j)
if(a[p[j]] < a[p[i]] || (a[p[j]] == a[p[i]] && b[p[j]] < b[p[i]])) swap(p[i], p[j]);
for(int i = ; i < n; ++i)
printf("%.5lf %.5lf %.5lf %.5lf %.5lf\n", a[p[i]].x, a[p[i]].y, b[p[i]].x, b[p[i]].y, Length(a[p[i]] - b[p[i]]));
}
} return ;
}
WA掉的代码君