引言 计算几何对于很多刚接触OI的同学们是不会涉及的，当逐步进入省选范畴之后，计算几何的应用就非常广了。 本文同 洛谷日报 #142。 你需要知道？ 在学习计算几何（至少是这篇文章）之前，你需要了解以下这...

前言 最小圆覆盖和最小矩形覆盖其实是有一定区别的。在矩形中有两组平行直线，在圆中则没有。 随机增量法 因为复杂度是在期望意义下计算的，所以无论题目给出什么样的数据，我们都要随机一下，这就是“随机”的...

半平面交好题。 Description The main land of Japan called Honshu is an island surrounded by the sea. In such an island, it is natural to ask a question: “Where is the most distant point fro...

前言 凸包和旋转卡壳都学了，平几就剩个半平面交了吧…… 感觉挺有用又听说很好学，于是就学了一下。 有点像线性规划吧。（和想象中有点差距 定义 半平面 一条直线和直线的一侧。半平面是一个点集，因此是一...

    感觉对旋转卡壳的理解又多了一点点……不过这个题莫名卡精度啊 题目描述 给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标 输入输出格式 输入格式： 第一行...

    以前的凸包可能是死记硬背的……不过现在算理解了。 凸包 定义     凸包就是求一个周长最小的，并且能包围所有给定点的多边形。当多边形表面存在凹陷时，根据三角不等式\(\left\{\begin{matrix}a+b>c\\ b...

    UVA提供各种输出格式坑 Description Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King’s castle. The King was so greedy, that he would no...

简单题目 POJ 2318 TOYS 题目链接 代码 对于一条线，它的上端点为 $A$，下端点为 $B$，如果 $\overrightarrow{CA}\times \overrightarrow{CB}>0$，说明点 $C$ 在 $AB$ 的右侧，否则在 $AB$ 左侧。并且由于点不...

      有点卡常？学会了\(O(n)\)建树状数组。 Description 红莉栖想要弄清楚楼下天王寺大叔的显像管电视对 “电话微波炉 (暂定)” 的影响. 选取显像管的任意一个平面, 一开始平面内有个\(n\)电子, 初始...

      要好好掌握斜率优化。   Description 小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要...