48分 求调
查看原帖
48分 求调
1781089
DZY_2025楼主2025/7/26 16:07
#include<bits/stdc++.h>
using namespace std;
const int N=110011;
typedef long long LL;
struct S{
	LL x,y;
}a[N];
LL n,m,u[N],v[N],sum[N];
LL lmax(LL x,LL y)
{
	if(x>y)return x;
	else return y;
}
int check(LL x,LL y)
{
	if(x>0&&y>0)return 1;
	if(x<0&&y>0)return 2;
	if(x<0&&y<0)return 3;
	if(x>0&&y<0)return 4;
	if(x>0&&y==0)return 5;
	if(x==0&&y>0)return 6;
	if(x<0&&y==0)return 7;
	if(x==0&&y<0)return 8;
	return 9;
} 
bool cmp(S l,S r)
{
	LL ax=l.x,ay=l.y,bx=r.x,by=r.y;
	if(check(ax,ay)<=4&&check(bx,by)<=4)
	{
		if(check(ax,ay)!=check(bx,by))
		return check(ax,ay)<check(bx,by);
		else if(check(ax,ay)==check(bx,by))
		{
            return ay*bx<by*ax;
		}
	}
	else if(check(ax,ay)>4&&check(bx,by)>4)
	 return check(ax,ay)<check(bx,by);
	else
	{
		if(check(ax,ay)>4)
		{
			if(check(ax,ay)-4<=check(bx,by))return true;
			return false;
		}
		else if(check(bx,by)>4)
		{
			if(check(ax,ay)<check(bx,by)-4)return true;
			return false;
		}
	}
}
bool equal(S l,S r)
{
	LL ax=l.x,ay=l.y,bx=r.x,by=r.y;
	if(check(ax,ay)!=check(bx,by))
	{
		return false;
	}
	else if(check(ax,ay)<=4)
	{
		return ay*bx==by*ax;
	}
	else 
	{
		return true;
	}
}
int lowerb(S s)
{
	int l=1,r=n+1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(cmp(a[mid],s))l=mid+1;
		else r=mid;
	}
	return l;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		sum[i]=1;
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i];
	}
	sort(a+1,a+n+1,cmp);
	int t=0;
//	for(int i=1;i<=n;i++)
//	{
//		cout<<a[i].x<<" "<<a[i].y<<endl;
//	}
	for(int i=2;i<=n;i++)
	{
		if(!cmp(a[i-1],a[i]))
		{
			t++;
			if(cmp(a[i],a[i+1]))
			{
				t++;
				LL k=t-1;
				while(k>=0)
				{
					sum[i-k]=t;
					k--;
				}
			}
		}

	}
	LL tu=1,tv=0;
	for(int i=1;i<=m;i++)
	{
		S l={tu,tv},r={u[i],v[i]},t={0,0};
		int s=lowerb(l),e=lowerb(r);
		
		//cout<<s<<" "<<e;
		if(s>e)
		{
			swap(s,e);
			t=l;l=r;r=t;
		}
		LL as=e-s,bs=n-e+sum[e]+s-1;
		if(equal(r,a[e]))
		{
			as+=sum[e];
		}
		if(equal(l,a[s]))
		{
			bs+=sum[s];
		}
		//cout<<" "<<as<<" "<<bs<<endl;
		cout<<lmax(as,bs)<<endl;
		tu=u[i];tv=v[i];
	}
	
	return 0;
}
2025/7/26 16:07
加载中...