跟我一起，成为计算几何大王八！

userId_undefined
prediction
秩序白银

2026-07-29 19:39:41

发布于：浙江

55阅读
0回复
0点赞

没想好。下午写基础的吧。

@cjdst，挂一个

致歉：本文部分MarkDown是DeepSeek完成的，因为帖主的水平实在菜菜。对不起。

Pt.1 前置知识

1.点

点的话可以看做地球上的你的位置，你所处的地方肯定可以用经纬度这种坐标来表示，那么点也要用一个坐标来表示，平面上的点用坐标表示为: P(x,y)\boldsymbol{P(x,y)}，其中 xx 和 yy 分别为横、纵坐标（不懂请自行学习平面直角坐标系的基础知识）。

点的模版

struct Point
{
    double x, y;
    Point(){}//无参构造
    Point(double x_,double y_):x(x_),y(y_){}//带参构造
};

无参构造允许直接定义变量不初始化，带参构造则可以快速创建点。

Point a(1.5,2.0);

这就是带参构造创建点。

两点 A(x1,y1),B(x2,y2)A(x_1,y_1),B(x_2,y_2) 之间的距离公式：dis=(x1−x2)2+(y1−y2)2dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

2.1向量

向量就是有大小，有方向，可平移的有向线段，类似于你家在马路上的汽车，虽然汽车不能平移，我们平常说的"25°C、10m、5cm25°C、10m、5cm"这种不是向量，向量代表长度加方向，例如向东走33米，速度向南3m/s3m/s。

在平面几何里，我们用带箭头的线段表示向量：

AB→\overrightarrow{AB} : 起点 AA ，终点 BB ，箭头指向 BB 。

坐标表示：AB→=B−A=(xB−xA, yB−yA)\overrightarrow{AB}=B-A=(x_B-x_A,\ y_B-y_A)

向量可以直接用Point结构体存储（计算几何惯例）

2.2向量的基础运算

设两个点 a(x1,y1),b(x2,y2)\boldsymbol{a}(x_1,y_1),\boldsymbol{b}(x_2,y_2)

1.加法：a+b=(x1+x2,y1+y2)a+b=(x_1+x_2,y_1+y_2)

2.减法：a−b=(x1−x2,y1−y2)a-b=(x_1-x_2,y_1-y_2)

3.数乘：k⋅a=(k⋅x1,k⋅y1)k\cdot\boldsymbol{a}=(k\cdot x_1,k\cdot y_1)

2.3向量的注意事项

1.向量没有固定起点，只有坐标，平移之后仍是同个向量

2.向量减法：终点 - 起点

3.浮点问题：全部使用double，禁止int直接参与几何运算

4.不要用角度或斜率判断位置关系，避免分母为 00 ，三角函数精度爆炸

5.精度处理：定义const double eps=1e-8;，只要两个数差距小于 epseps ，我们就认为这两数相等，这个 epseps 是 1×10−8=0.000000011\times 10^{-8} = \boldsymbol{0.00000001}

判断正负模版：

int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    return x>0:1:-1;
}

这里使用绝对值函数因为double类型有误差，直接用 ==== 判断极端情况下会出错。

Pt.2 点积和叉积

点积

点积就是数量积，设平面 22 个向量 a=(x1,y1),b=(x2,y2)\boldsymbol a=(x_1,y_1),\quad \boldsymbol b=(x_2,y_2)，那 a⋅b=x1x2+y1y2\boldsymbol a \cdot \boldsymbol b = x_1x_2 + y_1y_2，几何意义为 a⋅b=∣a∣∣b∣cos⁡θ\boldsymbol a\cdot\boldsymbol b=|\boldsymbol a||\boldsymbol b|\cos\theta，这里的 θ\theta 表示两个向量的夹角，这个东西的用处可以用来判断夹角大小，求向量模长平方 a⋅a=x12+y12=∣a∣2\boldsymbol a\cdot\boldsymbol a = x_1^2+y_1^2=|\boldsymbol a|^2 ，也可以求投影长度，感兴趣的可以自己查阅下资料（因为我菜菜讲不了）。

叉积

差积是向量积，设平面 2 个向量 a=(x1,y1),b=(x2,y2)\boldsymbol a=(x_1,y_1),\quad \boldsymbol b=(x_2,y_2)，有a×b=x1y2−x2y1\boldsymbol a \times \boldsymbol b = x_1y_2 - x_2y_1 ，这里的符号 ×× 不是我们用的 ∗* ，而是专门用来区分点积的。

叉积的几何意义为 a×b=∣a∣∣b∣sin⁡θ\boldsymbol a\times\boldsymbol b=|\boldsymbol a||\boldsymbol b|\sin\theta ，这里的绝对值为由 a,b 围成平行四边形的面积。

站在向量 a\boldsymbol a 终点看向 b\boldsymbol b ：

a×b>0\boldsymbol a \times \boldsymbol b > 0：b\boldsymbol b 在 a\boldsymbol a 逆时针左侧
a×b<0\boldsymbol a \times \boldsymbol b < 0：b\boldsymbol b 在 a\boldsymbol a 顺时针右侧
a×b=0\boldsymbol a \times \boldsymbol b = 0：两向量共线（同向 / 反向）

看一道例题。

[Concentric Circles] Adjacent Sums (easy)

题意
平面上，是否存在两个同心圆 C1,C2C_1,C_2（圆心相同，可以是同一个圆）满足：
P,QP,Q 两点落在 C1C_1 的圆周上；
R,SR,S 两点落在 C2C_2 的圆周上。

继续简化就是是否存在一个公共的圆心，使得 OP=OQ、OR=OSOP=OQ、OR=OS ，想做到这点，必须满足

OP=OQOP=OQ：OO 在线段 PQPQ 的垂直平分线上
OR=OSOR=OS：OO 在线段 RSRS 的垂直平分线上

问题就变成了两条垂直平分线是否有交点。

哇，真的好简洁。

设：
L1L_1：PQPQ 的垂直平分线
L2L_2：RSRS 的垂直平分线

如果他们平行且重合就说明有交点，相交也说明有交点。

设三点 A(x1,y1),B(x2,y2)A(x_1,y_1),B(x_2,y_2)，动点 O(x,y)O(x,y) ，垂直平分线的条件为 ∣OA∣2=∣OB∣2|OA|^2=|OB|^2 ，展开即得
(x−x1)2+(y−y1)2=(x−x2)2+(y−y2)2(x-x_1)^2+(y-y_1)^2 = (x-x_2)^2+(y-y_2)^2 ，再通过一系列的移项和整理（这里不过多概述），即可得到 2(x2−x1)x+2(y2−y1)y=x22+y22−x12−y122(x_2-x_1)x + 2(y_2-y_1)y = x_2^2+y_2^2 - x_1^2-y_1^2，也就是 Ax+By=C\boldsymbol{Ax + By = C} ，那么可得

L1L_1（PQPQ 垂直平分线）：A1x+B1y=C1A_1x+B_1y=C_1
L2L_2（RSRS 垂直平分线）：A2x+B2y=C2A_2x+B_2y=C_2

判别条件：D=A1B2−A2B1≠0D = A_1B_2 - A_2B_1 \neq 0 或者 D=A1B2−A2B1=0D = A_1B_2 - A_2B_1 = 0 (重合的平行) 就输出 YesYes ，否则输出 NoNo 。

这里的 DD 就是向量 (A1,A2)(A_1,A_2) 与 (B1,B2)(B_1,B_2) 的叉积。

#include <iostream>
using namespace syh;
typedef long long ll;
inline ll read()
{
    ll x=0, f=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar_unlocked();
    }
    return x*f;
}
void func(ll x1,ll x2,ll y1,ll y2,ll &a,ll &b,ll &c)
{
    ll x=x2-x1;
    ll y=y2-y1;
    a=2*x;
    b=2*y;
    c=x*(x1+x2)+y*(y1+y2);
}
int main()
{
    int t=read();
    while(t--)
    {
        ll px=read(), py=read(), qx=read(), qy=read();
        ll rx=read(), ry=read(), sx=read(), sy=read();
        ll a1, b1, c1, a2, b2, c2;
        func(px,qx,py,qy,a1,b1,c1);
        func(rx,sx,ry,sy,a2,b2,c2);
        __int128 d=(__int128)a1*b2-(__int128)a2*b1;
        if(d!=0)
        {
            cout<<"Yes"<<"\n";
            continue;
        }
        else
        {
            bool f=((__int128)a1*c2==(__int128)a2*c1)&&((__int128)b1*c2==(__int128)b2*c1);
            if(f) cout<<"Yes"<<"\n";
            else cout<<"No"<<"\n";
        }
    }
    return 0;
}

不知道为什么 long long 被卡了。

Pt.3 向量常用操作

bababababba

Pt.4 直线 & 线段

abababba

Pt.5 多边形基础

多边形面积（利用叉积）

判断点在多边形内部（射线法）

Pt.6 凸包 Andrew 算法

ababababa

P2742 圈奶牛（凸包求周长）

详见大佬的讲解

结束了

剩下的希望早点写完。

userId_undefined
去预览
0/2000

全部评论 4

热门讨论