计算几何

三点共线

A,B,C三点共线当且仅当AB⃗×AC⃗=0\vec{AB}\times \vec{AC}=0。

给定三点坐标A(x1,y1),B(x2,y2),C(x3,y3)A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)，则有AB⃗=(x2−x1,y2−y1)\vec{AB}=(x_2-x_1,y_2-y_1)，AC⃗=(x3−x1,y3−y1)\vec{AC}=(x_3-x_1,y_3-y_1)。

AB⃗×AC⃗=((x2−x1)(y3−y1)−(y2−y1)(x3−x1))\vec{AB}\times \vec{AC}=((x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)) 

1
2
3
4
bool areCollinear(int x1, int y1, int x2, int y2, int x3, int y3)//判断三点是否共线
{
    return (x2 - x1) * (y3 - y1) == (y2 - y1) * (x3 - x1);
}

点到线段的最短距离

给定三点坐标A(xa,ya),P(xp,yp),Q(xq,yq)A(x_a,y_a),P(x_p,y_p),Q(x_q,y_q)。

两点间距离

AP=(xa−xp)2+(ya−yp)2AP=\sqrt{(x_a-x_p)^2+(y_a-y_p)^2} 

1
2
3
4
double Point_to_Point(ll xa, ll ya, ll xp, ll yp)//两点间距离
{
    return sqrt((xa - xp) * (xa - xp) + (ya - yp) * (ya - yp));  
}

点到直线的距离

设直线方程为Ax+By+C=0Ax+By+C=0

不同两点P,QP,Q在直线上则：

A=yq−ypB=xp−xqC=xqyp−xpyqA=y_q-y_p \\ B=x_p-x_q \\ C=x_qy_p-x_py_q

d=∣Axa+Bxb+C∣A2+B2d=\frac{\left | Ax_a+Bx_b+C \right |}{\sqrt{A^2+B^2}} 

1
2
3
4
5
6
7
double Point_to_Line(ll xa, ll ya, ll xp, ll yp, ll xq, ll yq) // 点到直线距离
{
    double A = yq - yp;
    double B = xp - xq;
    double C = xq * yp - xp * yq;
    return fabs(A * xa + B * ya + C) / sqrt(A * A + B * B);
}

点的投影在线段上

如果点AA的投影在线段PQPQ上则$\angle{APQ} $ 和∠AQP\angle{AQP}均为锐角，也即余弦值大于等于零。

cos⁡∠APQ=PA⃗∙PQ⃗∣PA⃗∣∣PQ⃗∣\cos{\angle{APQ}}=\frac{\vec{PA} \bullet \vec{PQ}}{\left| \vec{PA}\right|\left| \vec{PQ}\right|}

PA⃗∙PC⃗=(xa−xp)(xq−xp)+(ya−yp)(yq−yp)\vec{PA} \bullet \vec{PC}=(x_a-x_p)(x_q-x_p)+(y_a-y_p)(y_q-y_p) 

1
2
3
4
5
6
bool TouYingOnLine(ll xa, ll ya, ll xp, ll yp, ll xq, ll yq) // 投影点在线段上
{
    double cosAPQ = (xa - xp) * (xq - xp) + (ya - yp) * (yq - yp);
    double cosAQP = (xa - xq) * (xp - xq) + (ya - yq) * (yp - yq);
    return cosAPQ >= 0 && cosAQP >= 0;
}

香蕉蕉蕉蕉，平行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Point{
    ll x,y;
    Point(ll x=0,ll y=0):x(x),y(y){}
};
typedef Point Vector;
struct Line{
    Vector v;//方向向量
    Point p;//直线上一点
    Line(Vector v,Point p):v(v),p(p){}
    Point point(double t){return p+v*t;}
};
struct Segment//线段
{
    Point A, B;
    Segment(Point A, Point B) : A(A), B(B) {}
};
struct Circle
{
	Point p;//圆心 
	double r;
	Circle(point A,double B){p = A, r = B;}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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-10;
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;}//叉积

直线

两直线方向向量外积为0则平行，反之香蕉。

1
2
3
4
5
6
7
8
9
10
//判断两直线是否平行
bool Parallel(Line a, Line b)
{
    return dcmp(Cross(a.v, b.v)) == 0;
}
//香蕉
bool Intersect(Line a, Line b)
{
    return !Parallel(a, b);
}

线段

c1∗c2<0c1*c2<0表示b.Ab.A和b.Bb.B在aa的两侧；

c3∗c4<0c3*c4<0表示a.Aa.A和a.Ba.B在bb的两侧；

c1=0c1=0表示b.Ab.A在aa上；

c2=0c2=0表示b.Bb.B在aa上；

c3=0c3=0表示a.Aa.A在bb上；

c4=0c4=0表示a.Ba.B在bb上；

1
2
3
4
5
6
7
8
9
// 判断线段相交
bool SegmentIntersect(Segment a, Segment b)
{	//a:AB b:CD
    double c1 = Cross(a.B - a.A, b.A - a.A);//AB X AC 
    double c2 = Cross(a.B - a.A, b.B - a.A);//AB X AD
    double c3 = Cross(b.B - b.A, a.A - b.A);//CD X CA
    double c4 = Cross(b.B - b.A, a.B - b.A);//CD X CB
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
1
2
3
4
5
// 判断线段平行
bool SegmentParallel(Segment a, Segment b)
{
    return dcmp(Cross(a.B - a.A, b.B - b.A)) == 0;//向量共线
}

三点求外接圆

1
2
3
4
5
6
7
8
9
10
Circle CircumscribedCircle(Point A, Point B, Point C)
{ // 外接圆
    double d = 2 * (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
    if (dcmp(d) <= 0)
        return Circle(Point(0, 0), 0); // 三点共线
    double x = ((A.x * A.x + A.y * A.y) * (B.y - C.y) + (B.x * B.x + B.y * B.y) * (C.y - A.y) + (C.x * C.x + C.y * C.y) * (A.y - B.y)) / d;
    double y = ((A.x * A.x + A.y * A.y) * (C.x - B.x) + (B.x * B.x + B.y * B.y) * (A.x - C.x) + (C.x * C.x + C.y * C.y) * (B.x - A.x)) / d;
    Point O = Point(x, y);
    return Circle(O, Length(O - A));
}

求简单多边形的面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll DoubleArea(vector<ll> x, vector<ll> y, int n)
{
    x[0] = x[n];
    x[n + 1] = x[1];
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans = ans + y[i] * (x[i + 1] - x[i - 1]);
    return ans > 0 ? ans : -1 * ans;
}
int main()
{
    int n;
    cin >> n;
    vector<ll> x(1010);
    vector<ll> y(1010);
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    cout << DoubleArea(x, y, n);
    return 0;
}