UVA 12304 - 2D Geometry 110 in 1!(計算幾何)

UVA 12304 - 2D Geometry 110 in 1!(計算幾何)

這題真的是惡心到爆炸啊

通過這題整理了下圓相關的計算幾何模板（基本都是參考別人的)

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) {
        this->x = x;
        this->y = y;
    }
    void read() {
        scanf("%lf%lf", &x, &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);
}

bool operator < (const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

const double eps = 1e-8;
const double PI = acos(-1.0);

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

bool operator == (const Point& a, const Point& b) {
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;} //點積
double Length(Vector A) {return sqrt(Dot(A, A));} //向量的模
double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Length(A) / Length(B));} //向量夾角
double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;} //叉積
double Area2(Point A, Point B, Point C) {return Cross(B - A, C - A);} //有向面積
double angle(Vector v) {return atan2(v.y, v.x);}

Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) {
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

Vector Rotate(Vector A, double rad) {
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}

double DistanceToLine(Point P, Point A, Point B) {
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2)) / Length(v1);
}

Vector AngleBisector(Point p, Vector v1, Vector v2){//給定兩個向量，求角平分線
    double rad = Angle(v1, v2);
    return Rotate(v1, dcmp(Cross(v1, v2)) * 0.5 * rad);
}

//求線與x軸的真實角(0<=X<180)
double RealAngleWithX(Vector a){
    Vector b(1, 0);
    if (dcmp(Cross(a, b)) == 0) return 0.0;
    else if (dcmp(Dot(a, b) == 0)) return 90.0;
    double rad = Angle(a, b);
    rad = (rad / PI) * 180.0;
    if (dcmp(a.y) < 0) rad = 180.0 - rad;
    return rad;
}

struct Circle {
    Point c;
    double r;
    Circle(Point c, double r) {
        this->c = c;
        this->r = r;
    }
    Point point(double a) {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
};

//求直線與圓的交點
int getLineCircleIntersection(Point p, Vector v, Circle c, vector &sol) {
    double a1 = v.x, b1 = p.x - c.c.x, c1 = v.y, d1 = p.y - c.c.y;
    double e1 = a1 * a1 +  c1 * c1, f1 = 2 * (a1 * b1 + c1 * d1), g1 = b1 * b1 + d1 * d1 - c.r * c.r;
    double delta = f1 * f1 - 4 * e1 * g1, t;
    if(dcmp(delta) < 0) return 0;
    else if(dcmp(delta) == 0){
        t = (-f1) / (2 * e1);
        sol.push_back(p + v * t);
        return 1;
    } else{
        t = (-f1 + sqrt(delta)) / (2 * e1); sol.push_back(p + v * t);
        t = (-f1 - sqrt(delta)) / (2 * e1); sol.push_back(p + v * t);
        return 2;
    }
}

//兩圓相交
int getCircleCircleIntersection(Circle C1, Circle C2, vector &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), p2 = C1.point(a + da);
    sol.push_back(p1);
    if(p1 == p2) return 1;
    sol.push_back(p2);
    return 2;

}

//點到圓的切線
int getTangents(Point p, Circle C, Vector *v) {
    Vector u = C.c - p;
    double dist = Length(u);
    if (dist < C.r) return 0;
    else if (dcmp(dist - C.r) == 0) {
        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;
    }
}

//兩圓公切線
//a[i], b[i]分別是第i條切線在圓A和圓B上的切點
int getCircleTangents(Circle A, Circle B, Point *a, Point *b) {
	int cnt = 0;
	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;
	double base = angle(B.c - A.c);
	//重合有無限多條
	if (d2 == 0 && dcmp(A.r - B.r) == 0) return -1;
	//內切
	if (dcmp(d2 - rdiff * rdiff) == 0) {
		a[cnt] = A.point(base);
		b[cnt] = B.point(base);
		cnt++;
		return 1;
	}
	//有外公切線
	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) == 0) {
		a[cnt] = A.point(base); b[cnt] = B.point(PI + base); cnt++;
    } else if (dcmp(d2 - rsum*rsum) > 0) {
		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++;
	}
	return cnt;
}

//三角形外切圓
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 = Point(cx, cy);
    return Circle(p, Length(p1 - p));
}

//三角形內切圓
Circle InscribedCircle(Point p1, Point p2, Point p3) {
    double a = Length(p2 - p3);
    double b = Length(p3 - p1);
    double c = Length(p1 - p2);
    Point p = (p1 * a + p2 * b + p3 * c) / (a + b + c);
    return Circle(p, DistanceToLine(p, p1, p2));
}

//求經過點p1,與直線(p2, w)相切,半徑為r的一組圓
int CircleThroughAPointAndTangentToALineWithRadius(Point p1, Point p2, Vector w, double r, vector &sol) {
    Circle c1 = Circle(p1, r);
    double t = r / Length(w);
    Vector u = Vector(-w.y, w.x);
    Point p4 = p2 + u * t;
    int tot = getLineCircleIntersection(p4, w, c1, sol);
    u = Vector(w.y, -w.x);
    p4 = p2 + u * t;
    tot += getLineCircleIntersection(p4, w, c1, sol);
    return tot;
}

//給定兩個向量，求兩向量方向內夾著的圓的圓心。圓與兩線均相切，圓的半徑已給定
Point Centre_CircleTangentTwoNonParallelLineWithRadius(Point p1, Vector v1, Point p2, Vector v2, double r){
    Point p0 = GetLineIntersection(p1, v1, p2, v2);
    Vector u = AngleBisector(p0, v1, v2);
    double rad = 0.5 * Angle(v1, v2);
    double l = r / sin(rad);
    double t = l / Length(u);
    return p0 + u * t;
}

//求與兩條不平行的直線都相切的4個圓，圓的半徑已給定
int CircleThroughAPointAndTangentALineWithRadius(Point p1, Vector v1, Point p2, Vector v2, double r, Point *sol) {
    int ans = 0;
    sol[ans++] = Centre_CircleTangentTwoNonParallelLineWithRadius(p1, v1, p2, v2, r);
    sol[ans++] = Centre_CircleTangentTwoNonParallelLineWithRadius(p1, v1 * -1, p2, v2, r);
    sol[ans++] = Centre_CircleTangentTwoNonParallelLineWithRadius(p1, v1, p2, v2 * -1, r);
    sol[ans++] = Centre_CircleTangentTwoNonParallelLineWithRadius(p1, v1 * -1, p2, v2 * -1, r);
    return ans;
}

//求與兩個相離的圓均外切的一組圓，三種情況
int CircleTangentToTwoDisjointCirclesWithRadius(Circle c1, Circle c2, double r, Point *sol){
    double dis1 = c1.r + r + r + c2.r;
    double dis2= Length(c1.c - c2.c);
    if(dcmp(dis1 - dis2) < 0) return 0;
    Vector u = c2.c - c1.c;
    double t = (r + c1.r) / Length(u);
    if(dcmp(dis1 - dis2)==0){
        Point p0 = c1.c + u * t;
        sol[0] = p0;
        return 1;
    }
    double aa = Length(c1.c - c2.c);
    double bb = r + c1.r, cc = r + c2.r;
    double rad = acos((aa * aa + bb * bb - cc * cc) / (2 * aa * bb));
    Vector w = Rotate(u, rad);
    Point p0 = c1.c + w * t;
    sol[0] = p0;
    w = Rotate(u, -rad);
    p0 = c1.c + w * t;
    sol[1] = p0;
    return 2;
}

char op[25];
Point p[4];
double r[3];

int main() {
    while (~scanf("%s", op)) {
        if (strcmp(op, "CircumscribedCircle") == 0) {
            for (int i = 0; i < 3; i++) p[i].read();
            Circle ans = CircumscribedCircle(p[0], p[1], p[2]);
            printf("(%.6f,%.6f,%.6f)\n", ans.c.x, ans.c.y, ans.r);
        } else if (strcmp(op, "InscribedCircle") == 0) {
            for (int i = 0; i < 3; i++) p[i].read();
            Circle ans = InscribedCircle(p[0], p[1], p[2]);
            printf("(%.6f,%.6f,%.6f)\n", ans.c.x, ans.c.y, ans.r);
        } else if (strcmp(op, "TangentLineThroughPoint") == 0) {
            p[0].read();
            scanf("%lf", &r[0]);
            p[1].read();
            Vector v[3];
            int tot = getTangents(p[1], Circle(p[0], r[0]), v);
            double ans[3];
            for (int i = 0; i < tot; i++)
                ans[i] = RealAngleWithX(v[i]);
            sort(ans, ans + tot);
            printf("[");
            for (int i = 0; i < tot; i++) {
                printf("%.6f", ans[i]);
                if (i != tot - 1) printf(",");
            }
            printf("]\n");
        } else if (strcmp(op, "CircleThroughAPointAndTangentToALineWithRadius") == 0) {
            for (int i = 0; i < 3; i++) p[i].read();
            scanf("%lf", &r[0]);
            vector ans;
            int tot = CircleThroughAPointAndTangentToALineWithRadius(p[0], p[1], p[2] - p[1], r[0], ans);
            sort(ans.begin(), ans.end());
            printf("[");
            for (int i = 0; i < tot; i++) {
                printf("(%.6f,%.6f)", ans[i].x, ans[i].y);
                if (i != tot - 1) printf(",");
            }
            printf("]\n");
        } else if (strcmp(op, "CircleTangentToTwoLinesWithRadius") == 0) {
            Point ans[4];
            for (int i = 0; i < 4; i++) p[i].read();
            scanf("%lf", &r[0]);
            int tot = CircleThroughAPointAndTangentALineWithRadius(p[0], p[1] - p[0], p[3], p[3] - p[2], r[0], ans);
            sort(ans, ans + tot);
            printf("[");
            for (int i = 0; i < tot; i++) {
                printf("(%.6f,%.6f)", ans[i].x, ans[i].y);
                if (i != tot - 1) printf(",");
            }
            printf("]\n");
        } else {
            p[0].read(); scanf("%lf", &r[0]);
            p[1].read(); scanf("%lf", &r[1]);
            scanf("%lf", &r[2]);
            Point ans[4];
            int tot = CircleTangentToTwoDisjointCirclesWithRadius(Circle(p[0], r[0]), Circle(p[1], r[1]), r[2], ans);
            sort(ans, ans + tot);
            printf("[");
            for (int i = 0; i < tot; i++) {
                printf("(%.6f,%.6f)", ans[i].x, ans[i].y);
                if (i != tot - 1) printf(",");
            }
            printf("]\n");
        }
    }
    return 0;
}