Z3phyrFT

算法学习

题解(2)

/ 注册

全部文章 / 算法学习（共3篇）

【计算几何】半平面交

半平面交算法对于平面上的所有有向边（角度范围）将向量按照角度排序(atan2(y,x)) 按顺序扫描所有向量，用双端队列维护双平面交轮廓只要队尾的两个线和队头的两个线的交点在当前直线的右侧（因为保存左侧），将队尾或者队头删除用直线的参数方程存储直线时间复杂度 int cnt; s...

计算几何

2021-08-03

0 427

【计算几何】二维凸包-Andrew算法

Andrew算法将所有点排序，x为第一关键字，y为第二关键字从左到右维护上半部分，从右至左维护下半部分栈顶反向延长线的顺时针方向就留下，反之删除栈顶 double andrew(){ sort(q,q+n); int top = 0; for (int i = 0;...

计算几何二维凸包

2021-08-01

0 625

计算几何的基本知识和模板

简单总结几何最重要的计算单位就是向量，可以使用pair<>来定义变量，或者自定义结构体（需要重载一些运算符）向量最重要的两个操作点积，用来计算向量夹角叉积，用来计算面积（方向性面积），通过不同点和一个线段的面积的正负可以判断这个点的相对直线的位置向量的旋转也是比较重要的内...

计算几何

2021-07-29

0 555