点的坐标

1. 直线的交点
   
   图中有四个顶点 A、B、C、D，组成两条直线 AB 和 CD，交点是 P。以下两个关系成立：
   
   联系上面两个方程，得到交点 P 的坐标如下：
   
   注意：在 Cross_point() 中要对（s2-s1）做除法，所以在调用 Cross_point() 之前应该保证 ，即直线 AB、CD 不共线，而且不平行。

2. 投影点
   已知直线上的两点 以及直线外的一点 ，求投影点 。
   
   令 ,即 k 是线段 长度的比值。
   因为 ，如果求得 k，就能得到 。
   根据点积的概念，有
   即 ，代入得
   
   所以，
   代码如下：

3. 对称点
   求一个点 对一条直线 的对称点（镜像点）。先求点 在直线上的投影 ，再求对称点 .
   

4. 直线与圆的交点
   先求圆心 c 在直线上的投影点 q，再求距离 d，然后根据 r 和 d 求出长度 k，最后求出两个交点 ，其中 n 直线的单位向量。

// 直线的交点
point point_cross_point(point a, point b, point c, point d) {
    double s1 = cross(b-a, c-a);
    double s2 = cross(b-a, d-a);              // 叉积有正负
    return (c*s2 - d*s1) / (s2 - s1);
}
// 投影点
point proj(point a, point b, point p) {
    return a + (b-a) * dot(p-a, b-a) / dot(b-a, b-a);
}
// 对称点
point symmetry(point a, point b, point p) {
    point q = proj(a, b, p);
    return point(2*q.x-p.x, 2*q.y-p.y);
}
// 直线与圆的交点
void line_cross_crecle(point a, point b, point c, double r, point &pa, point &pb) {
    point q = proj(a, b, c);
    double k = sqrt(r*r - dot(c-q, c-q));
    point n = (b-a) / sqrt(dot(b-a, b-a));
    pa = q + n*k, pb = q - n*k;
}

三角行外接圆

设一个圆的圆心 和半径 ，则这个圆可以表示为
在圆上随便取三点，三点坐标为 。那么有：



化简得：

// 三角形外接圆圆心
point circumcenter(point a, point b, point c) {
    point A(b.x-a.x, c.x-a.x);
    point B(b.y-a.y, c.y-a.y);
    point C(dot(b+a, b-a)/2, dot(c+a, c-a)/2);
    return point(cross(C, B), cross(A, C)) / cross(A, B);
}

多边形性质

1. 多边形面积
2. 多边形重心

// 多边形的面积
double polygon_area(point p[], int n, double area = 0) { 
    for(int i = 1; i <= n; ++ i) {
        area += cross(p[i], p[i%n+1]);
    }
    return area / 2;  // 面积有正负，不能取绝对值
}
// 多边形重心
point polygon_center(point p[], int n) {
    point ans(0, 0);
    if (polygon_area(p, n) == 0) return ans;
    for(int i = 1; i <= n; ++ i) {
        ans = ans + (p[i] + p[i%n+1]) * cross(p[i], p[i%n+1]);
    }
    return ans / polygon_area(p, n) / 6;
}

向量旋转

使向量（x,y）绕起点逆时针旋转，设旋转角度为\thetaθ ，那么旋转后的向量（X,Y）如下：
X = x * cos\thetaθ - y * sin\thetaθ
Y = x * sin\thetaθ + y * cos\thetaθ
特殊情况是旋转 90°
逆时针旋转90°：返回 Vector(-a.y, a.x)
顺时针旋转90°：返回 Vector( a.y, -a.x)
有时需要求单位法向量，即逆时针转90°，然后求单位值。

// 向量按中心（x，y）旋转
Vector rotate(Vector A, double rad, double x = 0, double y = 0) { // 向量按（x，y）旋转
    return Vector((A.x-x)*cos(rad)-(A.y-y)*sin(rad)+x, (A.x-x)*sin(rad)+(A.y-y)*cos(rad)+y);
}