首先可以题目描述的两个点集是两个凸包,分别设为A和B。
考虑一个向量w不合法的条件。
即存在b+w=a,其中a属于A,b属于B。
也就是a-b=w。
即对b取反后和a的闵可夫斯基和。
求出闵可夫斯基和后check点是否在凸包内即可,在凸包内说明不合法。

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 330000
#define L 300000
#define eps 1e-15
#define inf 1e18+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
int dcmp(db x){if(fabs(x)<=eps)return 0;else return (x>0)?+1:-1;}
struct vec
{
    db x,y;
    vec operator+(vec a){return (vec){x+a.x,y+a.y};}
    vec operator-(vec a){return (vec){x-a.x,y-a.y};}
    db ang(){return atan2(y,x);}
};
typedef vec pot;
db cross(vec a,vec b){return a.x*b.y-b.x*a.y;}
bool cmp_vec(vec a,vec b){return a.ang()<b.ang();}
bool cmp_pot(pot a,pot b){if(dcmp(a.x-b.x))return a.x<b.x;else return a.y<b.y;}
vec f[N];
pot a[N],b[N],p[N],t[N],v[N],s[N];
int main()
{   
    int n=read(),m=read(),qnum=read(),top,num,num_,cnt=0,tot=0;
    pot P={-inf,-inf},Q={-inf,-inf};
    for(int i=1;i<=n;i++)a[i].x=+read(),a[i].y=+read();
    num=0;sort(a+1,a+n+1,cmp_pot);top=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&dcmp(cross(s[top]-s[top-1],a[i]-s[top-1]))!=+1)top--;
        s[++top]=a[i];
    }
    for(int i=1;i<=top;i++)t[++num]=s[i];top=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&dcmp(cross(s[top]-s[top-1],a[i]-s[top-1]))!=-1)top--;
        s[++top]=a[i];
    }
    for(int i=top;i>=1;i--)t[++num]=s[i];num_=0;
    for(int i=1;i<=num;i++)
    {
        if(i==num&&!dcmp(t[i].x-t[1].x)&&!dcmp(t[i].y-t[1].y))continue;
        if(i!=1&&!dcmp(t[i].x-t[i-1].x)&&!dcmp(t[i].y-t[i-1].y))continue;
        v[++num_]=t[i];
    }
    for(int i=1;i<=num_;i++)
    {
        if(dcmp(v[i].y-P.y)==0&&dcmp(v[i].x-P.x)<0)P=v[i];
        if(dcmp(v[i].y-P.y)>0)P=v[i];
        if(i!=1)f[++cnt]=v[i]-v[i-1];if(i==num_)f[++cnt]=v[1]-v[i];
    }
    
    for(int i=1;i<=m;i++)b[i].x=-read(),b[i].y=-read();
    num=0;sort(b+1,b+m+1,cmp_pot);top=0;
    for(int i=1;i<=m;i++)
    {
        while(top>1&&dcmp(cross(s[top]-s[top-1],b[i]-s[top-1]))!=+1)top--;
        s[++top]=b[i];
    }
    for(int i=1;i<=top;i++)t[++num]=s[i];top=0;
    for(int i=1;i<=m;i++)
    {
        while(top>1&&dcmp(cross(s[top]-s[top-1],b[i]-s[top-1]))!=-1)top--;
        s[++top]=b[i];
    }
    for(int i=top;i>=1;i--)t[++num]=s[i];num_=0;
    for(int i=1;i<=num;i++)
    {
        if(i==num&&!dcmp(t[i].x-t[1].x)&&!dcmp(t[i].y-t[1].y))continue;
        if(i!=1&&!dcmp(t[i].x-t[i-1].x)&&!dcmp(t[i].y-t[i-1].y))continue;
        v[++num_]=t[i];
    }
    for(int i=1;i<=num_;i++)
    {
        if(dcmp(v[i].y-Q.y)==0&&dcmp(v[i].x-Q.x)<0)Q=v[i];
        if(dcmp(v[i].y-Q.y)>0)Q=v[i];
        if(i!=1)f[++cnt]=v[i]-v[i-1];if(i==num_)f[++cnt]=v[1]-v[i];
    }
    
    sort(f+1,f+cnt+1,cmp_vec);
    pot k=P+Q;p[++tot]=k;
    for(int i=1;i<=cnt;i++)
    {
        k=k+f[i];
        if(i!=cnt&&dcmp(f[i].x*f[i+1].y-f[i].y*f[i+1].x)==0)continue;
        p[++tot]=k;
    }
    tot--;k=p[1];
    for(int i=1;i<=qnum;i++)
    {
        pot o;
        o.x=read();o.y=read();
        if(dcmp(cross(p[2]-k,o-k))==-1||dcmp(cross(p[tot]-k,o-k))==+1){printf("0\n");continue;}
        int l=2,r=tot-1,mid;
        while(l<r)
        {
            mid=((l+r)>>1)+1; 
            if(dcmp(cross(p[mid]-k,o-k))==+1)l=mid;
            else r=mid-1;
        }
        if(dcmp(cross(p[l+1]-p[l],o-p[l]))!=-1)printf("1\n");else printf("0\n"); 
    }
    return 0;
}

转载于:https://www.cnblogs.com/Creed-qwq/p/10317720.html

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐