94pts 求调
查看原帖
94pts 求调
684131
VainSylphidElena楼主2024/12/19 15:40

破防了。倒闭了。回家了。

#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;
}
2024/12/19 15:40
加载中...