在上周的CCPC秦皇岛中，我们在热身赛就“出师不利”，被一道计算几何斩下马。所以我开始祈祷天堂没有计算几何（误），所以我开始主攻计算几何这一部分。在这篇BLOG中，我们就来一同解决长方体两点的最短表面距离这一看似简单实则十分繁杂的问题吧！由于这个问题在网络上的讨论甚少，仅有的一份CSDN上的模板也是错误的，所以本片BLOG也是没有任何参考的完全原创BLOG。如果本篇BLOG出现任何错误，欢...
好久没有更新计算几何的相关博客了。最近见到几道矩阵最大子矩形问题的题目，感觉可以拓展到计算几何上解决最大子矩形问题。下面就让我们逐一看看这些个问题吧。 矩阵最大子矩形问题 问题描述 在矩阵最大子矩形问题相关问题中，最出名的要数最大全零子矩形了。下面就让我们来看看问题描述。 题目大意：在一个给定的大小为a*b矩形网格中有n个障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子...
最近有些高产啊……咳咳咳……今天看到了一个非常实用的计算几何定理，决定带上简单易懂的证明分享给大家QwQ 什么是Pick定理 皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。 这个算法最早是由奥地利的的George Alexander Pick提出，为了纪念他，所以这个...
在之前的BLOG里，我们已经基本学完了计算几何的算法。可是仍然有一些题目是我们之前的算法所无法解决的。这时候我们就要使用计算几何的终极奥义——枚举和分治 :neckbeard:。 枚举与计算几何 先引入一道经典例题： [caioj 1211]统计正方形 题目描述 【题目描述】 给定平面上N个点,你需要计算以其中4个点为顶点的正方形的个数。注意这里的正方形边不一定需要和坐标轴平行。 【输...
不知不觉简单的计算几何就快讲完了，这次我再讲讲旋转卡壳算法（看得我脑袋是有些卡壳QwQ）。这个算法和凸包有着很大的关系，所以建议没看凸包的同学去计算几何分类看一下凸包的求解方法。 先抛出一个问题 在二维平面上给定n个点，求距离最远的两个点之间的距离是多少？ 看到这道题，大部分同学第一反应肯定是暴力——暴力枚举所有点对，然后求出最远的那一对相距的距离。这种方法当然没错，可是复杂度已经达到...