这题对于倍增来说会不会时限有点紧啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int N=1e6+5,inf=2e9,P=19;
ll getll()
{
	int x=0,y=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
	{
		if(c=='-')
		{
			y=-1;
		}
	}
	for(;c>='0'&&c<='9';c=getchar())
	{
		x=x*10+c-'0';
	}
	return x*y;
}
class Point
{
	public:
		ll x,y;
		Point(ll xx=0,ll yy=0)
		:x(xx),y(yy)
		{
		}
		void read()
		{
			x=getll();
			y=getll();
		}
		void out()
		{
			cout<<x<<" "<<y<<endl;
		}
		bool operator < (const Point &a)
		{
			return x==a.x?y<a.y:x<a.x;
		}
		Point operator + (const Point &a)
		{
			return Point(x+a.x,y+a.y);
		}
		Point operator - (const Point &a)
		{
			return Point(x-a.x,y-a.y);
		}
		ll operator | (const Point &a)
		{
			return x*a.x+y*a.y;
		}
		ll operator & (const Point &a)
		{
			return x*a.y-y*a.x;
		}
};
Point in[N];
int n;
void read()
{
	n=getll();
	for(int i=1;i<=n;i++)
	{
		in[i].read();
	}
}
int bao[N];int topb;
void getbao()
{
	topb=0;
	sort(in+1,in+n+1);
	for(int i=1;i<=n;i++)
	{
		for(;
		topb>1&&((in[bao[topb-1]]-in[bao[topb-2]])&(in[i]-in[bao[topb-1]]))<=0;
		topb--)
		{
		}
		bao[topb++]=i;
	}
	int t=topb;
	for(int i=n-1;i;i--)
	{
		for(;
		topb>t&&((in[bao[topb-1]]-in[bao[topb-2]])&(in[i]-in[bao[topb-1]]))<=0;
		topb--)
		{
		}
		bao[topb++]=i;
	}
	topb--;
/*	for(int i=0;i<topb;i++)
	{
		in[bao[i]].out();
	}*/
}
class node
{
	public:
		Point st,en;
		bool operator < (const node &a)
		{
			return (st&a.st)>0;
		}
};
node th[2*N];
void getsten()
{
	for(int i=0;i<n;i++)
	{
		int last=(i-1+n)%n,nxt=(i+1)%n;
		th[i].st=in[bao[i]]-in[bao[nxt]];
		th[i].en=in[bao[i]]-in[bao[last]];
	//	cout<<endl;th[i].st.out();th[i].en.out();cout<<endl;
	}
	int t=n;
	for(int i=0;i<n;i++)
	{
		th[t++]=th[i];
	}
}
class Use
{
	public:
		int w;
		int num;
		Use()
		{
		}
		Use(int ww,int nu)
		:w(ww),num(nu)
		{
		}
		Use operator + (const Use &a)
		{
			return Use(a.w,num+a.num);
		}
};
Use zeng[P+1][2*N];
int solve()
{
	getbao();
	if(topb<n)
	{
		return 3;
	}
	getsten();
	for(int i=0;i<2*n;i++)
	{
		zeng[0][i]=Use(i,1);
	}
	int h=1;
	for(int i=1;i<=P&&(1<<i)<=n;i++,h++)
	{
		bool can=0;
		for(int j=0,k=0;j<2*n;j++)
		{
			k=max(k,zeng[i-1][j].w);
			for(;k<2*n&&(th[zeng[i-1][j].w].en&th[k].st)<=0;k++)
			{
			}
			if((th[zeng[i-1][j].w].en&th[k-1].en)>0)
			{
				k--;
			}
			if(k==2*n)
			{
				zeng[i][j]=zeng[i-1][j];
			}else
			{
				zeng[i][j]=zeng[i-1][j]+zeng[i-1][k];
				if(zeng[i][j].w<=j+n)
				{
					can=1;
				}
			}
		}
		if(can==0)
		{
			break;
		}
	}
	h--;
	int minn=inf;
	for(int i=0;i<n;i++)
	{
		Use use=Use(i,1);
		int k=i;
		for(int j=h;j>=0;j--)
		{
			for(;k<2*n&&(th[use.w].en&th[k].st)<=0;k++)
			{
			}
			if((th[use.w].en&th[k-1].en)>0)
			{
				k--;
			}
			if(zeng[j][k].w>=i+n)
			{
				continue;
			}
			use=use+zeng[j][k];
			k=zeng[j][k].w;//cout<<zeng[j][k].w<<endl;
		}
		for(;k<2*n&&(th[use.w].en&th[k].st)<=0;k++)
		{
		}
		if((th[use.w].en&th[k-1].en)>0)
		{
			k--;
		}
		if((th[use.w].en&th[i].st)>0&&(th[i].st&th[k].st)<0&&(th[i].st&th[k].en)>0)
		{
			use.num++;
		}//cout<<endl;
		minn=min(minn,use.num);
	}
	return minn;
}
int main()
{
	int q;
	cin>>q;
	for(;q;q--)
	{
		read();
		if(n<=2)
		{
			cout<<0<<endl;
			continue;
		}
		cout<<solve()<<endl;
	}
}