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){     
继续阅读