计算几何——二维几何

以UVA12304 2D Geometry 110 in 1为例，介绍一些二维几何的知识。
基本概念：点乘+叉乘+向量长度+向量极角（atan2）+弧度转角度+角度转弧度+旋转向量（采用逆时针旋转公式）+单位化向量+单位法向量函数。
点和直线：点到直线的距离+点到线段的距离+点在线段上的投影+两直线交点+线段相交判定+点在线段上判定+多边形面积函数。
直线与圆：直线与圆的交点+两圆的交点+圆的切线+两圆的公共外切圆+与两直线相切的圆+与直线相切过定点的圆+内切圆+外接圆。

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;

Vector operator+(const Vector &A, const Vector &B) { 
    return Vector(A.x + B.x, A.y + B.y); 
}
Vector operator-(const Point &a, const Point &b) { 
    return Vector(a.x - b.x, a.y - b.y); 
}
Vector operator*(const Vector &A, double p) { 
    return Vector(A.x * p, A.y * p); 
}
Vector operator/(const 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-10;
int dcmp(double x) { 
    if (fabs(x) < eps) return 0; 
    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(const Vector &A, const Vector &B) { 
    return A.x * B.x + A.y * B.y; 
}
double Length(const Vector &A) { 
    return sqrt(Dot(A, A)); 
}
double Angle(const Vector &A, const Vector &B) { 
    return acos(Dot(A, B) / Length(A) / Length(B)); 
}
const double Pi = atan(1) * 4;
double Angle(const Vector &A) { 
    return atan2(A.y, A.x); 
}
double R_to_D(double rad) { 
    return 180 / Pi * rad; 
}
double D_to_R(double D) { 
    return Pi / 180 * D; 
}
double Cross(const Vector &A, const Vector &B) { 
    return A.x * B.y - A.y * B.x; 
}
double Area2(const Point &a, const Point &b, const Point &c) { 
    return Cross(b - a, c - a); 
}

Vector Rotate(const Vector &A, double rad) {
    double csr = cos(rad), sir = sin(rad);
    return Vector(A.x * csr - A.y * sir, A.x * sir + A.y * csr);
}
Vector Normal(const Vector &A) {
    double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}
Vector Format(const Vector &A) {
    double L = Length(A);
    return Vector(A.x / L, A.y / L);
}

Point GetLineIntersection(const Point &A1, const Point &B1, const Point &A2, const Point &B2) {
    Vector u = A1 - A2, v = B1 - A1, w = B2 - A2;
    double t = Cross(w, u) / Cross(v, w);
    return A1 + v * t;
}
double DistanceToLine(const Point &P, const Point &A, const Point &B) {
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2)) / Length(v1);
}
double DistanceToSegment(const Point &P, const Point &A, const Point &B) {
    if (A == B) return Length(P - A);
    Vector v1 = B - A, v2 = P - A, v3 = P - B;
    if (dcmp(Dot(v1, v2)) < 0) return Length(v2);
    else if (dcmp(Dot(v1, v3)) > 0) return Length(v3);
    else return fabs(Cross(v1, v2)) / Length(v1);
}
Point GetLineProjection(const Point &P, const Point &A, const Point &B) {
    Vector v = B - A;
    return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(const Point &a1, const Point &a2, const Point &b1, const Point &b2) {
    double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
           c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
bool OnSegment(const Point &p, const Point &a1, const Point &a2) { 
    return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0; 
}
double PolygonArea(Point* p, int n) {
    double area = 0;
    for (int i = 1; i < n - 1; i++)
        area += Cross(p[i] - p[0], p[i + 1] - p[0]);
    return area / 2;
}

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

int GetLineCircleIntersection(const Point &A, const Point &B, const Circle &C, vector<Point> &sol) {
    double d = DistanceToLine(C.c, A, B);
    int mode = dcmp(d - C.r);
    if (mode > 0) return 0;
    Point P = GetLineProjection(C.c, A, B);
    if (mode == 0) {
        sol.push_back(P);
        return 1;
    }
    double dist = sqrt(C.r * C.r - d * d);
    Vector v = Format(B - A);
    sol.push_back(P - v * dist);
    sol.push_back(P + v * dist);
    return 2;
}

int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point> &sol) {
    if (C1.r < C2.r) swap(C1, C2);
    double D = Length(C1.c - C2.c);
    if (dcmp(D) == 0)
        return dcmp(C1.r - C2.r) == 0 ? -1 : 0;
    if (dcmp(C1.r + C2.r - D) < 0) return 0;
    if (dcmp(fabs(C1.r - C2.r) - D) > 0) return 0;
    double d1 = ((C1.r * C1.r - C2.r * C2.r) / D + D) / 2;
    double x = sqrt(C1.r * C1.r - d1 * d1);
    Point O = C1.c + Format(C2.c - C1.c) * d1;
    Point P1 = O + Normal(O - C2.c) * x, P2 = O - Normal(O - C2.c) * x;
    sol.push_back(P1);
    if (P1 == P2) return 1;
    sol.push_back(P2);
    return 2;
}

int GetTangents(const Point P, const Circle C, vector<Point> &v) {
    Vector u = C.c - P;
    double dist = Length(u);
    int mode = dcmp(dist - C.r);
    if (mode < 0) return 0;
    if (mode == 0) {
        v.push_back(P + Normal(u));
        return 1;
    }
    double x = sqrt(dist * dist - C.r * C.r);
    Circle C2(P, x);
    return GetCircleCircleIntersection(C, C2, v);
}

Circle WaiJieYuan(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 ansx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x;
    double ansy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y;
    Point p(ansx, ansy);
    return Circle(p, Length(p1 - p));
}

Circle NeiJieYuan(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));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(6);
    
    string cmd;
    while (cin >> cmd) {
        if (cmd == "CircumscribedCircle") {
            double x1, y1, x2, y2, x3, y3;
            cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
            Point p1(x1, y1), p2(x2, y2), p3(x3, y3);
            Circle C = WaiJieYuan(p1, p2, p3);
            cout << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
        }
        else if (cmd == "InscribedCircle") {
            double x1, y1, x2, y2, x3, y3;
            cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
            Point p1(x1, y1), p2(x2, y2), p3(x3, y3);
            Circle C = NeiJieYuan(p1, p2, p3);
            cout << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
        }
        else if (cmd == "TangentLineThroughPoint") {
            
            double cx, cy, cr, px, py;
            cin >> cx >> cy >> cr >> px >> py;
            Circle C(Point(cx, cy), cr);
            Point p(px, py);
            vector<Point> v;
            vector<double> res;
            GetTangents(p, C, v);
            for (int i = 0; i < v.size(); i++) {
                double tmp = R_to_D(Angle(v[i] - p));
                if (tmp < 0) tmp += 180;
                if (tmp >= 180) tmp -= 180;
                res.push_back(tmp);
            }
            sort(res.begin(), res.end());
            cout << "[";
            for (int i = 0; i < res.size(); i++) {
                if (i) cout << ",";
                cout << res[i];
            }
            cout << "]" << endl;
        }
        else if (cmd == "CircleThroughAPointAndTangentToALineWithRadius") {
            //直线平移，以P为圆心求交点
            double px, py, ax, ay, bx, by, r;
            cin >> px >> py >> ax >> ay >> bx >> by >> r;
            Point p(px, py), A(ax, ay), B(bx, by);
            Circle C(p, r);
            Vector v = Normal(B - A) * r;
            Point A1 = A + v, B1 = B + v;
            Point A2 = A - v, B2 = B - v;
            vector<Point> res;
            GetLineCircleIntersection(A1, B1, C, res);
            GetLineCircleIntersection(A2, B2, C, res);
            sort(res.begin(), res.end());
            res.erase(unique(res.begin(), res.end()), res.end());
            cout << "[";
            for (int i = 0; i < res.size(); i++) {
                if (i) cout << ",";
                cout << "(" << res[i].x << "," << res[i].y << ")";
            }
            cout << "]" << endl;
        }
        else if (cmd == "CircleTangentToTwoLinesWithRadius") {
            //两直线平移将求圆心化为求交点 
            double x1, y1, x2, y2, x3, y3, x4, y4, r;
            cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 >> r;
            Point p1(x1, y1), p2(x2, y2), p3(x3, y3), p4(x4, y4);
            Vector v = Normal(p1 - p2) * r;
            Point A1 = p1 + v, B1 = p2 + v;
            Point A2 = p1 - v, B2 = p2 - v;
            v = Normal(p3 - p4) * r;
            Point A3 = p3 + v, B3 = p4 + v;
            Point A4 = p3 - v, B4 = p4 - v;
            vector<Point> res;
            res.push_back(GetLineIntersection(A1, B1, A3, B3));
            res.push_back(GetLineIntersection(A1, B1, A4, B4));
            res.push_back(GetLineIntersection(A2, B2, A3, B3));
            res.push_back(GetLineIntersection(A2, B2, A4, B4));
            sort(res.begin(), res.end());
            cout << "[";
            for (int i = 0; i < res.size(); i++) {
                if (i) cout << ",";
                cout << "(" << res[i].x << "," << res[i].y << ")";
            }
            cout << "]" << endl;
        }
        else if (cmd == "CircleTangentToTwoDisjointCirclesWithRadius") {
            //将题目转化为以C1为圆心C1.r+r的圆与以C2为圆心C2.r+r的圆求交点
            double cx1, cy1, cr1, cx2, cy2, cr2, r;
            cin >> cx1 >> cy1 >> cr1 >> cx2 >> cy2 >> cr2 >> r;
            Circle c1(Point(cx1, cy1), cr1);
            Circle c2(Point(cx2, cy2), cr2);
            c1.r += r;
            c2.r += r;
            vector<Point> res;
            GetCircleCircleIntersection(c1, c2, res);
            sort(res.begin(), res.end());
            cout << "[";
            for (int i = 0; i < res.size(); i++) {
                if (i) cout << ",";
                cout << "(" << res[i].x << "," << res[i].y << ")";
            }
            cout << "]" << endl;
        }
    }
    
    return 0;
}

牢