Tag-凸包

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-08-04 16:38:46 |  0 Comments  |  计算几何 凸包

SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置

题目大意

平面直角坐标系上有n个黑点和m个白点,判断能否用一条直线将黑点和白点分成互不相交的两部分。

题解

这题一眼望去就是个裸凸包+判断是否在凸包内。

但是我们要多考虑一些事情,就做一下分类讨论。

如果没有黑点或者没有白点,那么肯定是可以分开的。

如果黑点和白点都只有一个,那么判断一下黑点和白点是否重合。

如果其中一个有两个,另一种有1个,那么我们要判断后者的点是否在前者两个点所在的线段上。

具体的话,就是如下这样子:

if(cnt1 == 1 && cnt2 == 2){
    if(cross(st[1]-sp[1],st[1] - sp[2]) == 0 && mul(sp[1] - st[1],sp[1] - sp[2]) >= 0)
        flag = false;
}
else if(cnt1 == 2 && cnt2 == 1){
    if(cross(sp[1] - st[1],sp[1] - st[2]) == 0 && mul(st[1] - sp[1],st[1] - st[2]) >= 0)
        flag = false;
}

然后如果这两个集合都是组成一条线段的话,则判断两条线段是否相交(使用叉积)

如果以上情况都不满足,那么我们就直接求出两个凸包,然后分别判断两个集合的点是否在另一个集合所有点的凸包中,如果在,就输出NO,否则输出YES。

最终复杂度是O(n+nlogn)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
typedef long long ll;
struct point{
    int x,y;
}p[maxn],q[maxn],st[maxn],sp[maxn];
int cross(point a,point b){
    return a.x * b.y - b.x * a.y;
}
point operator - (point a,point b){
    point t;
    t.x = a.x - b.x;
    t.y = a.y - b.y;
    return t;
}
bool operator == (point a,point b){
    return (a.x == b.x &&
Title - Artist
0:00