永远鲜红的幼月

计算几何学习

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 图论(11) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 未归档(192) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 贪心(1) 题解(1)

/ 注册

全部文章 / 计算几何学习（共17篇）

解析几何--面积的计算

前提提要：向量叉积以后改用 ^ 符号，重载运算符后发现表示更清晰。 friend double operator ^ (Point a,Point b){ return a.x*b.y-a.y*b.x; } 三角形面积的计算。 1.解析几何法：由众多三角形的面积公式得出的结果： ...

2019-02-27

0 1467

解析几何--交点的计算

这个专题讨论用解析几何的方法解决线段，直线和点的计算问题。默认使用笛卡尔直角坐标系。计算点到线段的最近点。已知线段P1P2（（x1，y1），（x2，y2）），点Q（x0，y0），求点Q到线段P1P2的最近坐标。存在两种情况： 1.情况一：y1=y2&&x1！=x2...

2019-02-26

0 650

半平面交题目汇总

在此处总结关于半平面交的题目（基本都是POJ的）：目录 POJ-1279-Art Gallery（测板子） POJ-1474-Video Surveillance（测半平面相交板子） POJ-1755-（NO AC） POJ-2104-（NO AC） POJ-2187-（NO AC） ...

2019-02-25

0 582

计算几何基础--半平面求交

半平面，平面的一半。半平面求交，就是求得n个半平面的相交的平面。一开始可能不太好理解。举个例子：一条线，有两个半平面两条线，四个半平面，有一个相三条线，7个半平面，然后有一个相交的区域，这个区域就是半平面 ...

2019-02-24

0 670

计算几何基础--线段的性质

线段的计算。也是计算几何的基础之一。判断两线段相交，求交点，等都是必不可少的内容。常用的解析几何方法使用三角函数和除法，使得计算的代价较高&&容易产生较大的误差。如计算两条近似平行的直线y=kx+b，的交点，涉及到了除法运算。那么对计算机的精确度要求就非常高了。因此如果能够在计...

2019-02-21

0 705

计算几何基础--判断点的位置

点的定位点的定位属于几何查找，是计算几何中的一个重要的问题。其包括点在三角形内外，多边形内外判断，平面剖分中的位置等。关于出现在这篇文章中但没有给出的自定义函数，如：CroMul(V a,V b)等，上篇博客有提到，向量叉乘。判断点是否在线上：我们可以用刚刚我们提到的叉积重要性质，即...

2019-02-20

0 783

计算几何基础--规范数据表示

计算几何中的数据表示：为了规范代码的格式，整理一下数据的表示格式：本文中都用a（x1，y1），b（x2，y2）和c表示向量。向量加减法：设二维向量a(x1,y1),向量b(x2,y2).向量c。向量的加法：c=a+b=（x1+x2，y1+y2）; 因为向量是矢量，带有方向，因此...

2019-02-20

0 460