计算几何之判断线段相交

C++

判断线段相交可以用到之前讲的判断点与线段的位置关系的来实现。两条线段相交的充要条件是：两条线段都满足“另一 …

C++

判断向量之间的方向关系，可以使用叉乘、点乘来判断。如图所示，展现了点与向量之间的五种关系（相同除外）对于第 …

C++

映像就是点p关于线段p1,p2对称的点x 求映像就要先求出p在线段上的投影点pp，然后把p投影点pp的向量放大 …

C++

点在线段上的投影问题：已知一条线段，以及线外的一个点p，求p在线段上的投影点。这个问题可以这样处理：把p与 …

C++

直线点乘为0则正交，直线叉乘为0则平行。题目：CGL_2_A 代码：转载请注明来源：https://www …

C++

之前学了用普里姆算法来求最小生成树的权值和，但是它的时间复杂度为O(|V2|)，使用优先级队列优化后，可以优化 …

C++

求一棵树的直径的方法就是，从一个顶点出发，找到离它最远的顶点s，然后从顶点s出发，找离他最远的节点t.那么，s …

C++

在连通图G中，如果删除了某个点u之后，得到的子图不连通，那么点u就被称为关节点。求关节点可以用dfs来求。 …

C++

有向无环图可以用来表示各种事物的顺序，比如工作顺序。一些事情必须在另一些事情完成之后才能开始进行。那么，为了获 …

C++

之前学单源最短路径的时候，学到狄克斯特拉算法，我在想，如果对每个顶点都求它的单源最短路径，那不就可以得到全点对 …