Uva - 12304 - 2D Geometry 110 in 1!
题意：在二维平面上求解6个子问题：
1.三角形的外接圆；
2.三角形的内切圆；
3.点到圆的切线；
4.过定点且与定直线相切的半径为r的圆；
5.同时与两相交直线相切的半径为r的圆；
6.同时与两相离圆相切的半径为r的圆。
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24008
——>>做到第4小问的时候，出现了一个精度问题：本来用dcmp(delta) == 0来判断直线与圆相切，可以在此处硬是不正确。。。书中有言：“圆和直线相切的判定很容易受到误差影响，因为这里的直线是计算出来的，而不是题目中输入的。”。。。所以——“特殊判断圆心到输入直线的距离”（“当然也可以通过调整eps的数值来允许一定的误差，但不推荐这样做。调节eps只是掩盖了问题，并没有消除“）。
代码虽长，但1A啦。。。
#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn = 50;const double eps = 1e-10; //调到1e-6以上第4问就可以用delta判断切线,但《训练指南》建议，尽量不要调epsconst double pi = acos(-1);char type[maxn];int dcmp(double x){ return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);}struct Point{ double x; double y; Point(double x = 0, double y = 0):x(x), y(y){} bool operator < (const Point& e) const{ return dcmp(x - e.x) < 0 || (dcmp(x - e.x) == 0 && dcmp(y - e.y) < 0); } bool operator == (const Point& e) const{ return dcmp(x - e.x) == 0 && dcmp(y - e.y) == 0; } int read(){ return scanf("%lf%lf", &x, &y); }}p[3];typedef Point Vector;Vector operator + (Point A, Point B){ return Vector(A.x + B.x, A.y + B.y);}Vector operator - (Point A, Point B){ return Vector(A.x - B.x, A.y - B.y);}Vector operator * (Point A, double p){ return Vector(A.x * p, A.y * p);}Vector operator / (Point A, double p){ return Vector(A.x / p, A.y / p);}struct Line{ Point p; Point v; Line(){} Line(Point p, Point v):p(p), v(v){} int read(){ return scanf("%lf%lf%lf%lf", &p.x, &p.y, &v.x, &v.y); } Point point(double t){ return p + v * t; }};struct Circle{ Point c; double r; Circle(){} Circle(Point c, double r):c(c), r(r){} int read(){ return scanf("%lf%lf%lf", &c.x, &c.y, &r); } Point point(double a){ return Point(c.x + r * cos(a), c.y + r * sin(a)); }};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 - B.x * A.y;}double Length(Vector A){ return sqrt(Dot(A, A));}Vector Rotate(Vector A, double rad){ return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));}Vector Normal(Vector A){ double L = Length(A); return Vector(-A.y / L, A.x / L);}double DistanceToLine(Point P, Point A, Point B){ //点到直线的距离 Vector v1 = B - A; Vector v2 = P - A; return fabs(Cross(v1, v2) / Length(v1));}double angle(Vector v){ //求向量的极角 return atan2(v.y, v.x);}Point GetLineIntersection(Line l1, Line l2){ //求两直线的交点（前提：相交） Vector u = l1.p - l2.p; double t = Cross(l2.v, u) / Cross(l1.v, l2.v); return l1.point(t);}int getLineCircleIntersection(Line l, Circle C, double& t1, double& t2, vector<Point>& sol){ //求直线与圆的交点 double a = l.v.x; double b = l.p.x - C.c.x; double c = l.v.y; double d = l.p.y - C.c.y; double e = a * a + c * c; double f = 2 * (a * b + c * d); double g = b * b + d * d - C.r * C.r; double delta = f * f - 4 * e * g; double dist = DistanceToLine(C.c, l.p, l.p+l.v); if(dcmp(dist - C.r) == 0){ //相切，此处需特殊判断，不能用delta t1 = t2 = -f / (2 * e); sol.push_back(l.point(t1)); return 1; } if(dcmp(delta) < 0) return 0; //相离 else{ //相交 t1 = (-f - sqrt(delta)) / (2 * e); sol.push_back(l.point(t1)); t2 = (-f + sqrt(delta)) / (2 * e); sol.push_back(l.point(t2)); return 2; }}int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){ //求圆与圆的交点 double d = Length(C1.c - C2.c); if(dcmp(d) == 0){ if(dcmp(C1.r - C2.r) == 0) return -1; //两圆重合 return 0; //同心圆但不重合 } if(dcmp(C1.r + C2.r - d) < 0) return 0; //外离 if(dcmp(fabs(C1.r - C2.r) - d) > 0) return 0; //内含 double a = angle(C2.c - C1.c); double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d)); Point p1 = C1.point(a + da); Point p2 = C1.point(a - da); sol.push_back(p1); if(p1 == p2) return 1; //外切 sol.push_back(p2); return 2;}Circle CircumscribedCircle(Point p1, Point p2, Point p3){ //求三角形的外心 double Bx = p2.x - p1.x, By = p2.y - p1.y; double Cx = p3.x - p1.x, Cy = p3.y - p1.y; double D = 2 * (Bx * Cy - By * Cx); double cx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x; double cy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y; Point p(cx, cy); return Circle(p, Length(p1-p));}Circle InscribedCircle(Point p1, Point p2, Point p3){ //求三角形的内切圆 double a = Length(p3 - p2); double b = Length(p3 - p1); double c = Length(p2 - p1); Point p = (p1 * a + p2 * b + p3 * c) / (a + b + c); return Circle(p, DistanceToLine(p, p2, p3));}int TangentLineThroughPoint(Point p, Circle C, Vector *v){ //求点到圆的直线 Vector u = C.c - p; double dist = Length(u); if(dcmp(dist - C.r) < 0) return 0; else if(dcmp(dist - C.r) < eps){ v[0] = Rotate(u, pi / 2); return 1; } else{ double ang = asin(C.r / dist); v[0] = Rotate(u, ang); v[1] = Rotate(u, -ang); return 2; }}void CircleThroughAPointAndTangentToALineWithRadius(Point p, Point p1, Point p2, double r){ Vector AB = p2 - p1; Vector change1 = Rotate(AB, pi / 2) / Length(AB) * r; Vector change2 = Rotate(AB, -pi / 2) / Length(AB) * r; Line l1(p1 + change1, AB); Line l2(p1 + change2, AB); vector<Point> sol; sol.clear(); double t1, t2; int cnt1 = getLineCircleIntersection(l1, Circle(p, r), t1, t2, sol); int cnt2 = getLineCircleIntersection(l2, Circle(p, r), t1, t2, sol); int cnt = cnt1 + cnt2; if(cnt) sort(sol.begin(), sol.end()); printf("["); for(int i = 0; i < cnt; i++){ printf("(%.6f,%.6f)", sol[i].x, sol[i].y); if(cnt == 2 && !i) printf(","); } puts("]");}void CircleTangentToTwoLinesWithRadius(Point A, Point B, Point C, Point D, double r){ Vector AB = B - A; Vector change = Normal(AB) * r; Point newA1 = A + change; Point newA2 = A - change; Vector CD = D - C; Vector update = Normal(CD) * r; Point newC1 = C + update; Point newC2 = C - update; Point p[5]; p[0] = GetLineIntersection(Line(newA1, AB), Line(newC1, CD)); p[1] = GetLineIntersection(Line(newA1, AB), Line(newC2, CD)); p[2] = GetLineIntersection(Line(newA2, AB), Line(newC1, CD)); p[3] = GetLineIntersection(Line(newA2, AB), Line(newC2, CD)); sort(p, p + 4); printf("["); printf("(%.6f,%.6f)", p[0].x, p[0].y); for(int i = 1; i < 4; i++){ printf(",(%.6f,%.6f)", p[i].x, p[i].y); } puts("]");}void CircleTangentToTwoDisjointCirclesWithRadius(Circle C1, Circle C2, double r){ Vector CC = C2.c - C1.c; double rdist = Length(CC); if(dcmp(2 * r - rdist + C1.r + C2.r) < 0) puts("[]"); else if(dcmp(2 * r - rdist + C1.r + C2.r) == 0){ double ang = angle(CC); Point A = C1.point(ang); Point B = C2.point(ang + pi); Point ret = (A + B) / 2; printf("[(%.6f,%.6f)]\n", ret.x, ret.y); } else{ Circle A = Circle(C1.c, C1.r + r); Circle B = Circle(C2.c, C2.r + r); vector<Point> sol; sol.clear(); GetCircleCircleIntersection(A, B, sol); sort(sol.begin(), sol.end()); printf("[(%.6f,%.6f),(%.6f,%.6f)]\n", sol[0].x, sol[0].y, sol[1].x, sol[1].y); }}int main(){ while(scanf("%s", type) == 1){ if(strcmp(type, "CircumscribedCircle") == 0){ Point p1, p2, p3; p1.read(); p2.read(); p3.read(); Circle ret = CircumscribedCircle(p1, p2, p3); printf("(%f,%f,%f)\n", ret.c.x, ret.c.y, ret.r); } else if(strcmp(type, "InscribedCircle") == 0){ Point p1, p2, p3; p1.read(); p2.read(); p3.read(); Circle ret = InscribedCircle(p1, p2, p3); printf("(%f,%f,%f)\n", ret.c.x, ret.c.y, ret.r); } else if(strcmp(type, "TangentLineThroughPoint") == 0){ Circle C; Point p; C.read(); p.read(); Vector v[3]; int cnt = TangentLineThroughPoint(p, C, v); double ret[3]; for(int i = 0; i < cnt; i++){ ret[i] = angle(v[i]); if(dcmp(ret[i] - pi) == 0) ret[i] = 0; if(dcmp(ret[i]) < 0) ret[i] += pi; } sort(ret, ret + cnt); printf("["); for(int i = 0; i < cnt; i++){ printf("%.6f", ret[i] / pi * 180); if(cnt == 2 && !i) printf(","); } puts("]"); } else if(strcmp(type, "CircleThroughAPointAndTangentToALineWithRadius") == 0){ Point p, p1, p2; double r; p.read(); p1.read(); p2.read(); scanf("%lf", &r); CircleThroughAPointAndTangentToALineWithRadius(p, p1, p2, r); } else if(strcmp(type, "CircleTangentToTwoLinesWithRadius") == 0){ Point A, B, C, D; double r; A.read(); B.read(); C.read(); D.read(); scanf("%lf", &r); CircleTangentToTwoLinesWithRadius(A, B, C, D, r); } else{ Circle C1, C2; double r; C1.read(); C2.read(); scanf("%lf", &r); CircleTangentToTwoDisjointCirclesWithRadius(C1, C2, r); } } return 0;}