icontofig | 发布于 2019-08-04 16:38:46 | 阅读量 249 | 计算几何 凸包
发布于 2019-08-04 16:38:46 | 计算几何 凸包
SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置
题目大意平面直角坐标系上有n个黑点和m个白点,判断能否用一条直线将黑点和白点分成互不相交的两部分。 题解这题一眼望去就是个裸凸包+判断是否在凸包内。 但是我们要多考虑一些事情,就做一下分类讨论。 如果没有黑点或者没有白点,那么肯定是可以分开的。 如果黑点和白点都只有一个,那么判断一下黑点和白点是否重合。 如果其中一个有两个,另一种有1个,那么我们要判断后者的点是否在前者两个点所在的线段上。 具体的话,就是如下这样子: if(cnt1 == 1 && cnt2 == 2){     
继续阅读
icontofig | 发布于 2019-06-06 17:27:01 | 阅读量 339 | 三分 计算几何
发布于 2019-06-06 17:27:01 | 三分 计算几何
Codeforces Gym 101981 D Country Meow 三维计算几何
题目大意给出n个点的三维空间坐标,在空间内找任意一个点使得其距离这n个点中的最远的点的欧几里得距离最小。 题解说实话,马上考期末了应该复习来着,但是总是感觉不写完这篇心里闷得慌…… 这题实际上应该是个最小覆盖球,不过此篇博客不打算使用这种算法来做,这里介绍一种比较纯数学的方法去做。 我们假设我们选的点为P(x,y,z), 那么距离的平方的表达式一定为 如果固定其中的x,y,那么这个式子就是关于z的一个二次函数,且是有极小值的二次函数。 对于x,y当然也是同理的。 我们要求的就是所有距离的平方的最大值的最小值,于是就是求取极小值的一个过程。 众所周知二次函数是个单峰函数,最小值就是极小值,而单
继续阅读