Z3phyrFT

分类

算法学习(8) 题解(2)

/ 注册

全部文章（共5篇）

【计算几何】半平面交

半平面交算法对于平面上的所有有向边（角度范围）将向量按照角度排序(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

【题解】POJ3304Segments-计算几何

POJ3304 大致题意给定个线段，求是否存在一条直线，所有的线段在该直线上的投影都有一个公共点。思路题目可以转化为，是否存在一条直线可以穿过所有的线段。我们可以将所有的线段的两个端点全部存在一个数组里，任取两个不同的点构成直线，判断这条直线是否穿过所有线段。如果有一条这样的线段存在就输出Ye...

计算几何

2021-07-29

0 540

【题解】POJ2318Toys-计算几何

POJ2318 大致题意给定一个矩阵的四个顶点坐标，和矩阵内的条直线和个点，求每个被直线分成的区域内各包含多少点思路对于条边，我们通过二分查找到当前点右边的第一条边（因为点不可能存在于边上）就是该点所存在的区域。我们可以通过这个点和边的有向面积的正负判断点在线段的哪个方位。代码 #inclu...

计算几何

2021-07-29

0 564

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

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

计算几何

2021-07-29

0 552