SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置
计算几何 凸包   发布于 2019-08-04   307人围观  0条评论
计算几何 凸包   发表于 2019-08-04   307人围观  0条评论

题目大意

平面直角坐标系上有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 && a.y == b.y);
}
bool operator != (point a,point b){
    return (a.x != b.x || a.y != b.y);
}
int mul(point a,point b){
    return a.x * b.x + a.y * b.y;
}
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
bool cmp(point a,point b){
    return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
int graham(point pnt[],int n,point res[]){
    int top = 1;
    int len;
    sort(pnt+1,pnt+n+1,cmp);
    res[1] = pnt[1];
    if(n == 1)return 1;
    res[2] = pnt[2];
    if(n == 2)return 2;
    top++;
    for(int i = 3;i <= n;++i){
        while(top > 1 && cross(pnt[i] - res[top-1],res[top] - res[top-1]) <= 0){
            top -= 1;
        }
        res[++top] = pnt[i];
    }
    len = top;
    for(int i = n - 1;i >= 1;i--){
        while(top > len && cross(pnt[i] - res[top-1],res[top] - res[top-1]) <= 0){
            top -= 1;
        }
        res[++top] = pnt[i];
    }
    if(n > 1)top -= 1;
    return top;
}
int n,m;
int cnt1,cnt2;
bool check(point pnt[],int cnt,point x){
    int l = 2,r = cnt - 1,mid;
    while(l <= r){
        mid = (l + r) >> 1;
        int a1 = cross(pnt[mid] - pnt[1],x - pnt[1]);
        int a2 = cross(pnt[mid+1] - pnt[1],x - pnt[1]);
        if(a1 <= 0 && a2 >= 0){
            if(cross(pnt[mid+1] - pnt[mid],x - pnt[mid]) <= 0)return true;
            return false;
        }
        else if(a1 > 0) r = mid - 1;
        else l = mid + 1;
    }
    return false;
}
int main(){
    while(true){
        n = get_num();
        m = get_num();
        memset(p,0,sizeof(p));
        memset(q,0,sizeof(q));
        memset(st,0,sizeof(st));
        memset(sp,0,sizeof(sp));
        cnt1 = cnt2 = 0;
        if(n == 0 && m == 0)break;
        for(int i = 1;i <= n;++i){
            p[i].x = get_num();
            p[i].y = get_num();
        }
        for(int i = 1;i <= m;++i){
            q[i].x = get_num();
            q[i].y = get_num();
        }
        if(n == 0 || m == 0 || (n == 1 && m == 1 && p[1] != q[1])){
            printf("YES\n");
            continue;
        }
        cnt1 = graham(p,n,st);
        cnt2 = graham(q,m,sp);
        bool flag = true;
        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;
        }
        else if(cnt1 == 2 && cnt2 == 2){
            for(int i = 1;i <= 2;++i)
                for(int j = 1;j <= 2;++j)
                    if(sp[i] == st[j]){
                        flag = false;
                        break;
                    }
            int a1 = cross(st[1] - sp[1],st[1] - sp[2]);
            int a2 = cross(st[2] - sp[1],st[2] - sp[2]);
            if((a1 < 0 && a2 > 0) || (a1 > 0 && a2 < 0))
                flag = false;
        }
        else{
            if(cnt1 > 2){
                for(int i = 1;i <= cnt2;++i){
                    if(check(st,cnt1,sp[i])){
                        flag = false;
                        break;
                    }
                }
            }
            if(cnt2 > 2){
                for(int i = 1;i <= cnt1;++i){
                    if(check(sp,cnt2,st[i])){
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 upd:后来发现这样做其实好像是不对的,应该再加上判断凸包之间是否有线段相交,不过数据过水就让上面的程序也过了,大家就把这个程序当作凸包和判断点在凸包内的板子吧QAQ

上一篇: 2019 Multi-University Training Contest 1004 equation 思维题

下一篇: HDU 1512 Monkey King 左偏树 并查集

立即登录,发表评论
没有帐号?立即注册
0 条评论