永远鲜红的幼月

计算几何

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) 计算几何学习(17) 贪心(1) 题解(1)

/ 注册

全部文章 / 计算几何（共4篇）

POJ-1066-Treasure Hunt（线段相交）

题目链接：http://poj.org/problem?id=1066 题目大意：一个100*100的房间，里面有n个墙，题目保证不会有三个墙交于一个点。问离开房间的最少穿墙次数（包括房间的墙壁）思路：n的范围很小，枚举所有顶点，然后找到最小的即可。 ACCode： //#pragma ...

2019-04-10

0 738

POJ-1556-The Doors（DP+线段相交）

题目链接：http://poj.org/problem?id=1556 题目大意：给出一个10*10的房间，从坐标(0,5)到(10,5)问最短的距离是多少，中间有n个墙，每个墙有两个门，人只能从门进出。思路：一开始想着暴力所有路线，发现似乎会TLE，想了会发现可以用DP（贪心？）的思路解决。...

2019-03-29

0 428

平面扫描--线段树维护的扫描线

久闻扫描线算法的大名，趁着最近学习计算几何，学习一波扫描线。扫描线就是将一个图形进行扫描，从上到下||从左到右。一段一段的扫描，每扫描到一个位置，刷新一下记录的属性。直接说可能比较抽象，用一张图片来理解可能会更好：如图所示，我们有三个矩形（红，绿，蓝）我们如何对他进行扫描呢？有两种方法，...

2019-03-12

0 703

多边形面积求和

ACM中计算几何是常考的一个题型，这里总结一下比较常见的多边形面积求和问题：三角形的面积公式： S=0.5*AB*AC 这里以原点（0,0）为三角形的一个顶点。向量叉乘：a*b=x1y2-x2y1 S= （x1y2-x2y1）/2 多边形就是多个三角形相加，因为是向量叉乘，因此自身带有正负...

2019-01-18

0 693