永远鲜红的幼月

分类

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

/ 注册

全部文章（共315篇）

POJ-2318-TOYS（二分+线段相交）

题目链接：http://poj.org/problem?id=2318 题目大意：给出一个盒子，然后从左到右给出n条线，将盒子划分成了n+1个格子，然后再给出m个点，判断每个点在那个格子中。思路：从左上角到每一个点拉一根线，然后判断与每个格子的边缘的线是否相交。一开始我用的暴力，一个个线判断T...

2019-03-25

0 387

Codeforces Round #547 (Div. 3) A（分解质因数）B（思维）C（规律）D（简单模拟）E（简单模拟）F1，F2（大胆暴力）G（贪心）

A - Game 23（分解质因数）题目链接：https://codeforces.com/contest/1141/problem/A 题目大意：给出两个数a，b，通过*2||*3的操作能否让a变成b，如果可以，输出最小的变化次数。不行就输出-1 思路：判断b是否是a的倍数，然后看倍数是否...

2019-03-25

0 427

HDU-4807-Lunch Time(二分+费用流，思维)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4807 题目大意：n个点，m条边，k个人从点0到点n-1。有向图（题目中没有说）每条边长度1，有最大的人流承受量。人的速度是1.求所有人都到n-1点的时间。思路：一开始的时候以为是最大流，写了个板子...

2019-03-24

0 492

HDU-4803-Poor Warehouse Keeper（贪心+二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4803 题目大意：给出两个数x，y。有两种操作， 1.将x+1，同时y+y/x; 2.x不变，y+1；问最少操作多少次，能够将1，1，变为x，y。如果不能够变成x，y形式，输出-1。思路...

2019-03-21

0 536

HDU-1007-Quoit Design（最近点对，分治）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007 题目大意：给出n个点，输出这n个点中最近距离的两个点的距离/2。思路：数据范围不允许暴力，那么就开始想有什么更高效的算法，具体的代码推断自行百度。分治的思路。算法大致流程： Ste...

2019-03-19

0 790

POJ-2079-Triangle（凸包+旋转卡壳，暴力）

题目链接：http://poj.org/problem?id=2079 题目大意：给出n个点，然后求出这n个点中能够围城的三角形面积的最大值的三个点，输出面积。思路：首先易得三个点都位于凸包上。然后我们枚举凸包上的每个点i。然后j=i+1，k=j+1，旋转k点，直到得到最大的三角形，此时旋转j...

2019-03-15

0 450

POJ-2187-Beauty Contest（凸包+旋转卡壳板子）

题目链接：http://poj.org/problem?id=2187 题目大意：给出n个点，让你从中找出一对距离最大的点，输出(距离^2)。思路：将这些点构成一个凸包，易得最大距离的点对在凸包上，因此我们对这个凸包进行旋转卡壳，然后维护最大值即可。 ACCode： //#pragma ...

2019-03-13

0 524

凸包问题--旋转卡壳

前情提要： 1978年，M.I.Shamos在论文《Computational Ceometry》中介绍了一种寻找凸多边形直径的线性算法。 Shamos的算法就像绕着多边形旋转一对卡壳，因此便有了术语——旋转卡壳。旋转卡壳是一种高效的算法。被广泛运用在解决一些与凸包相关的问题。旋转卡壳充分利用了...

2019-03-13

0 1405

扫描线有关习题

总结一下关于扫描线的习题。正在更新中... Table of Contents HDU-1542-Atlantis，POJ-1151-Atlantis（扫描线+线段树） HDU-1255-覆盖的面积（扫描线+线段树，板子） HDU-1828-Picture||POJ-1177 Picture...

2019-03-12

0 824

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

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

2019-03-12

0 703