模板题

代码

#include<bits/stdc++.h>
#define N 200010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef  pair<int,int> pp;
struct Point
{
    LL x,y;
    bool operator < (const Point &a)const
    {return (x-a.x)<0 || ((x-a.x)==0 && (y-a.y)<0);}
    Point(LL x=0,LL y=0):x(x),y(y){ }
    void read(){scanf("%lld%lld",&x,&y);}
};
typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
LL Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}  //点积
//凸包
/*************************************************************** * 输入点数组p， 个数为p， 输出点数组ch。 返回凸包顶点数 * 希望凸包的边上有输入点，把两个<= 改成 < * 高精度要求时建议用dcmp比较 * 输入点不能有重复点。函数执行完以后输入点的顺序被破坏 ****************************************************************/
int ConvexHull(Point *p, int n, Point* ch) {
    sort(p, p+n);      //先比较x坐标，再比较y坐标
    int m = 0;
    for(int i = 0; i < n; i++) {
        while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i--) {
        while(m > k && Cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    return m;
}
//点在线段上（包含端点），在为 1 ，不在为 0
bool isPointOnSegment(Point P,Point A,Point B)
{
    return (Cross(A-P,B-P))==0 && (Dot(A-P,B-P))<=0;  // 不包含端点时为 <0
}
//判断点在凸包内模板 O（logn）
//凸包为逆时针
//在边界，返回0，在内部，返回1，在外部，返回-1
int check(Point A,Point*p,int n )
{
    if (isPointOnSegment(A,p[0],p[1])) return 0; // 包含端点
    if (isPointOnSegment(A,p[0],p[n-1])) return 0;
    int l=1,r=n-2,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        LL a1=Cross(p[mid]-p[0],A-p[0]);
        LL a2=Cross(p[mid+1]-p[0],A-p[0]);
        if(a1>=0&&a2<=0)
        {
            LL tmp=Cross(p[mid+1]-p[mid],A-p[mid]);
            if (tmp>0)return 1;
            if (tmp==0) return 0;
            return -1;
        }
        else if(a1<0)r=mid-1;else l=mid+1;
    }
    return -1;
}

Point a[N],b[N],c[N];
int Minkowski(Point *a,int n,Point *b,int m,Point *c){
    int t=0,x=1,y=1;
    c[t++]=a[0]+b[0]; a[n]=a[0],b[m]=b[0];
    while(x<=n&&y<=m)
        if (Cross(a[x]-a[x-1],b[y]-b[y-1])>0) 
            c[t]=c[t-1]+a[x]-a[x-1],t++,x++;
        else
            c[t]=c[t-1]+b[y]-b[y-1],t++,y++;
    while(x<=n) c[t]=c[t-1]+a[x]-a[x-1],t++,x++;
    while(y<=m) c[t]=c[t-1]+b[y]-b[y-1],t++,y++;
    return t-1;
}

int main(int argc, char const *argv[])
{
    int n,m,q;
    sccc(n,m,q);
    for(int i=0;i<n;i++) a[i].read();
    for(int i=0;i<m;i++) b[i].read(),b[i].x*=-1,b[i].y*=-1;
    n=ConvexHull(a,n,c);
    memcpy(a,c,sizeof(Point)*(n));
    m=ConvexHull(b,m,c);
    memcpy(b,c,sizeof(Point)*(m));
    int p=Minkowski(a,n,b,m,c);
    while(q--){
        Point x; x.read();
        int t=check(x,c,p);
        if (t==-1) puts("0");else puts("1");
    }
    return 0;
}