破防了。倒闭了。回家了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q;
struct Point{
ll x,y;
Point operator +(const Point& p) const
{
return {x + p.x,y + p.y};
}
Point operator -(const Point& p) const
{
return {x - p.x,y - p.y};
}
}a[300005],b[300005],s1[300005],s2[300005],c[300005];
ll cross(Point p1,Point p2)
{
return p1.x * p2.y - p1.y * p2.x;
}
ll dis(Point p1,Point p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmp1(Point A,Point B)
{
ll x = cross(A - a[1],B - a[1]);
return x == 0 ? dis(a[1],A) < dis(a[1],B) : x > 0;
}
bool cmp2(Point A,Point B)
{
ll x = cross(A - b[1],B - b[1]);
return x == 0 ? dis(b[1],A) < dis(b[1],B) : x > 0;
}
bool cmp3(Point A,Point B)
{
ll x = cross(A - c[1],B - c[1]);
return x == 0 ? dis(c[1],A) < dis(c[1],B) : x > 0;
}
int main()
{
//freopen("z3.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&q);
//convex A
for(ll i = 1;i <= n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
for(ll i = 1;i <= n;i++)
if(a[i].y < a[1].y)
swap(a[1],a[i]);
sort(a + 2,a + 1 + n,cmp1);
ll pa = 1;
for(ll i = 2;i <= n;i++)
{
while(pa > 1 && cross(a[pa] - a[pa - 1],a[i] - a[pa]) <= 0)
pa--;
a[++pa] = a[i];
}
n = pa;
/*for(ll i = 1;i <= n;i++)
printf("%lld %lld\n",a[i].x,a[i].y);
printf("\n");*/
//convex B
for(ll i = 1;i <= m;i++)
scanf("%lld%lld",&b[i].x,&b[i].y),b[i].x = -b[i].x,b[i].y = -b[i].y;
for(ll i = 1;i <= m;i++)
if(b[i].y < b[1].y)
swap(b[1],b[i]);
sort(b + 2,b + 1 + m,cmp2);
ll pb = 1;
for(ll i = 2;i <= m;i++)
{
while(pb > 1 && cross(b[pb] - b[pb - 1],b[i] - b[pb]) <= 0)
pb--;
b[++pb] = b[i];
}
m = pb;
/*printf("\n");
for(ll i = 1;i <= m;i++)
printf("%lld %lld\n",b[i].x,b[i].y);
printf("\n");*/
//minkowski
for(ll i = 1;i <= n;i++)
s1[i] = a[i % n + 1] - a[i];
for(ll i = 1;i <= m;i++)
s2[i] = b[i % m + 1] - b[i];
c[1] = a[1] + b[1];
ll p1 = 1,p2 = 1,tot = 1;
while(p1 <= n && p2 <= m)
if(cross(s1[p1],s2[p2]) >= 0)
tot++,c[tot] = c[tot - 1] + s1[p1],p1++;
else
tot++,c[tot] = c[tot - 1] + s2[p2],p2++;
while(p1 <= n)
tot++,c[tot] = c[tot - 1] + s1[p1],p1++;
while(p2 <= m)
tot++,c[tot] = c[tot - 1] + s2[p2],p2++;
/*printf("\n");
for(ll i = 1;i <= tot;i++)
printf("%lld %lld\n",c[i].x,c[i].y);
printf("\n");*/
for(ll i = 1;i <= tot;i++)
if(c[i].y < c[1].y)
swap(c[1],c[i]);
sort(c + 2,c + 1 + tot,cmp3);
ll pc = 1;
for(ll i = 2;i <= tot;i++)
{
while(pc > 1 && cross(c[pc] - c[pc - 1],c[i] - c[pc]) <= 0)
pc--;
c[++pc] = c[i];
}
/*printf("\n");
for(ll i = 1;i <= pc;i++)
printf("%lld %lld\n",c[i].x,c[i].y);
printf("\n");*/
Point base = c[1];
// printf("%lld %lld\n",base.x,base.y);
//printf("\n");
for(ll i = pc;i;i--)
c[i] = c[i] - base;
/*printf("\n");
for(ll i = 1;i <= pc;i++)
printf("%lld %lld\n",c[i].x,c[i].y);
printf("\n");*/
for(ll i = 1;i <= q;i++)
{
Point d;
scanf("%lld%lld",&d.x,&d.y);
d = d - base;
//printf(" %lld %lld\n",d.x,d.y);
if(cross(d,c[2]) > 0 || cross(c[pc],d) > 0 || (cross(d,c[2]) == 0 && dis(d,c[1]) > dis(c[1],c[2])) || (cross(c[pc],d) == 0 && dis(d,c[1]) > dis(c[1],c[pc])))
printf("0\n");
else
{
ll ql = 2,qr = pc;
while(ql <= qr)
{
ll mid = ql + qr >> 1;
if(cross(d,c[mid]) >= 0)
qr = mid - 1;
else
ql = mid + 1;
}
//printf(" %lld %lld\n",c[qr].x,c[qr].y);
if(cross(d - c[qr],c[qr + 1] - c[qr]) <= 0)
printf("1\n");
else
printf("0\n");
}
}
return 0;
}