半平面交学习笔记

定义

一条直线可以把平面分为两部分，其中一半的平面就叫半平面

而多个半平面的交集就叫做半平面交

这个交集可以是凸多边形、无穷平面、直线、线段、点等

一般来说，我们规定直线的左侧为我们需要的半平面

为了区别左右，直线应该是有方向的

算法流程

(1)、将所有直线按照极角从小到大排序，如果有极角相同的则保留左侧的

(2)、用一个双端队列存储当前半平面交,每次通过判断队首与队尾第一个交点是否满足当前直线来更新

(3)、先用队尾判定队首交点是否合法,再用队首判断队尾交点是否合法

(4)、最后求出来的半平面交是一个凸多边形

一定要先弹队尾再弹队首

原因

代码

P4196 [CQOI2006]凸多边形 /【模板】半平面交

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e3+5;
const double eps=1e-12,INF=1e5;
int dcmp(rg double now){
	return (std::fabs(now)<=eps)?0:(now>0?1:-1);
}
//为了减小精度误差，我们用自定义的比较函数
struct Node{
	double x,y;
	Node(){}
	Node(rg double aa,rg double bb){
		x=aa,y=bb;
	}
	friend Node operator +(const Node& A,const Node& B){
		return Node(A.x+B.x,A.y+B.y);
	}//向量+向量
	friend Node operator -(const Node& A,const Node& B){
		return Node(A.x-B.x,A.y-B.y);
	}//向量-向量
	friend Node operator *(const Node& A,const double& B){
		return Node(A.x*B,A.y*B);
	}//向量*浮点数
	friend Node operator /(const Node& A,const double& B){
		return Node(A.x/B,A.y/B);
	}//向量/浮点数
	friend double operator *(const Node& A,const Node& B){
		return A.x*B.x+A.y*B.y;
	}//点积
	friend double operator ^(const Node& A,const Node& B){
		return A.x*B.y-B.x*A.y;
	}//叉积
	double angle(){
		return atan2(y,x);
	}//求极角
}q2[maxn];
struct Line{
	Node s,t;
	//两点式,一条从s指向t的直线
	double ang;
	Line(rg Node aa=Node(),rg Node bb=Node()){
		s=aa,t=bb,ang=(bb-aa).angle();
	}//初始化
	friend bool operator <(const Line& A,const Line& B){
		double r=A.ang-B.ang;
		if(dcmp(r)==0) return dcmp((A.t-A.s)^(B.t-A.s))==-1;
		return dcmp(r)==-1;
	}//将直线进行排序
	friend double operator *(const Line& A,const Line& B){
		return (A.t-A.s)^(B.t-B.s);
	}
}q1[maxn],sta[maxn];
bool judline(rg Line aa,rg Line bb){
	return dcmp(aa*bb)==0;
}//判断两条直线是否共线，即叉积是否为零
bool onright(rg Line aa,rg Node bb){
	return dcmp((aa.t-aa.s)^(bb-aa.s))==-1;
}//判断点是否在直线右边
Node getsi(rg Line aa,rg Line bb){
	return aa.s+(aa.t-aa.s)*(((bb.t-bb.s)^(aa.s-bb.s))/(aa*bb));
}//两条直线交点
int head,tail,tp;
double getarea(){
	rg double nans=0;
	q2[tail+1]=q2[head];
	for(rg int i=head;i<=tail;i++){
		nans+=(q2[i]^q2[i+1]);
	}
	return std::fabs(nans/2.0);
}//算面积
bool SI(){
	std::sort(sta+1,sta+tp+1);//排序
	head=tail=0;
	q1[0]=sta[1];//将第一条直线入栈
	for(rg int i=2;i<=tp;i++){
		if(dcmp(sta[i].ang-sta[i-1].ang)!=0){//如果两条直线极角不相同
			if(head<tail && (judline(q1[head],q1[head+1]) || judline(q1[tail],q1[tail-1]))) return 0;//如果两条直线共线，并且极角不同，则没有半平面交
			while(head<tail && onright(sta[i],q2[tail-1])) tail--;//如果队尾的交点在新加入的直线的右边，就把点弹出队列
			while(head<tail && onright(sta[i],q2[head])) head++;//对于队首同理
			q1[++tail]=sta[i];//将新的直线放进队列里
			if(head<tail) q2[tail-1]=getsi(q1[tail],q1[tail-1]);//更新直线交点
		}
	}
	while(head<tail && onright(q1[head],q2[tail-1])) tail--;//删去多余点
	while(head<tail && onright(q1[tail],q2[head])) head++;
	if(tail-head<=1) return 0;//没有半平面交
	q2[tail]=getsi(q1[head],q1[tail]);
	return 1;
}
double solve(){
	sta[++tp]=Line(Node(-INF,-INF),Node(INF,-INF));
	sta[++tp]=Line(Node(INF,-INF),Node(INF,INF));
	sta[++tp]=Line(Node(INF,INF),Node(-INF,INF));
	sta[++tp]=Line(Node(-INF,INF),Node(-INF,-INF));//加入最大限制，防止半平面交无限大
	if(!SI()) return 0;
	return getarea();
}
int t,n;
double jlx[maxn],jly[maxn];
int main(){
	t=read();
	while(t--){
		n=read();
		for(rg int i=1;i<=n;i++){
			jlx[i]=read(),jly[i]=read();
		}
		jlx[0]=jlx[n],jly[0]=jly[n];
		for(rg int i=0;i<n;i++){
			sta[++tp]=Line(Node(jlx[i],jly[i]),Node(jlx[i+1],jly[i+1]));
		}
	}
	printf("%.3f
",solve());
	return 0;
}

习题

一、P3222 [HNOI2012]射箭

题目传送门

分析

设抛物线的解析式为 (y=ax^2+bx)

则对于每一条线段，都必须满足

(y_{i1} leq ax_i^2+bx_i leq y_{i2})

即 (ax_i^2+bx_i-y_{i1} geq 0)

(ax_i^2+bx_i-y_{i2} leq 0)

把 (a,b) 分别看成 (x,y) 就是一个半平面的形式

二分闯到第几关然后判断是否存在半平面交即可

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=3e5+5;
long double eps=1e-16,INF=1e12;
int dcmp(rg long double now){
	return std::fabs(now)<=eps?0:(now>0?1:-1);
}
struct Node{
	long double x,y;
	Node(){}
	Node(rg long double aa,rg long double bb){
		x=aa,y=bb;
	}
	friend Node operator -(rg const Node& A,rg const Node& B){
		return Node(A.x-B.x,A.y-B.y);
	}
	friend Node operator +(rg const Node& A,rg const Node& B){
		return Node(A.x+B.x,A.y+B.y);
	}
	friend Node operator *(rg const Node& A,rg const long double& B){
		return Node(A.x*B,A.y*B);
	}
	friend Node operator /(rg const Node& A,rg const long double& B){
		return Node(A.x/B,A.y/B);
	}
	friend long double operator *(rg const Node& A,rg const Node& B){
		return A.x*B.x+A.y*B.y;
	}
	friend long double operator ^(rg const Node& A,rg const Node& B){
		return A.x*B.y-B.x*A.y;
	}
	friend bool operator ==(rg const Node& A,rg const Node& B){
		return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;
	}
	long double angle(){
		return atan2(y,x);
	}
}q2[maxn];
struct Line{
	Node s,t;
	int id;
	long double ang;
	Line (rg Node A=Node(),rg Node B=Node(),rg int C=0){
		s=A,t=B,ang=(B-A).angle(),id=C;
	}
	friend bool operator <(rg const Line& A,rg const Line& B){
		rg long double r=A.ang-B.ang;
		if(dcmp(r)!=0) return dcmp(r)==-1;
		return dcmp((A.t-A.s)^(B.t-A.s))==-1;
	}
	friend long double operator *(rg const Line& A,rg const Line& B){
		return (A.t-A.s)^(B.t-B.s);
	}
}sta[maxn],q1[maxn];
int tp=0,head,tail,n;
bool judline(rg Line aa,rg Line bb){
	return dcmp(aa*bb)==0;
}
bool onright(rg Line aa,rg Node bb){
	return dcmp((aa.t-aa.s)^(bb-aa.s))<0;
}
Node getsi(rg Line aa,rg Line bb){
	return aa.s+(aa.t-aa.s)*(((bb.t-bb.s)^(aa.s-bb.s))/((aa.t-aa.s)^(bb.t-bb.s)));
}
bool SI(rg int mids){
	rg int now=1;
	head=tail=0;
	while(sta[now].id>mids) now++;
	q1[0]=sta[now++];
	for(rg int i=now;i<=tp;i++){
		if(sta[i].id>mids) continue;
		if(dcmp(sta[i].ang-sta[i-1].ang)!=0){
			if(head<tail && (judline(q1[head],q1[head+1]) || judline(q1[tail],q1[tail-1]))) return 0;
			while(head<tail && onright(sta[i],q2[tail-1])) tail--;
			while(head<tail && onright(sta[i],q2[head])) head++;
			q1[++tail]=sta[i];
			if(head<tail) q2[tail-1]=getsi(q1[tail],q1[tail-1]);
		}
	}
	while(head<tail && onright(q1[head],q2[tail-1])) tail--;
	while(head<tail && onright(q1[tail],q2[head])) head++;
	if(tail-head<=1) return 0;
	return 1;
}
int main(){
	n=read();
	if(n<=10) eps=1e-14;
	rg int aa,bb,cc;
	for(rg int i=1;i<=n;i++){
		aa=read(),bb=read(),cc=read();
		sta[++tp]=Line(Node(0,(long double)bb/(long double)aa),Node(1,(long double)bb/(long double)aa-(long double)aa),i);
		sta[++tp]=Line(Node(1,(long double)cc/(long double)aa-(long double)aa),Node(0,(long double)cc/(long double)aa),i);
	}
	sta[++tp]=Line(Node(-INF,eps),Node(-eps,eps),0);
	sta[++tp]=Line(Node(-eps,eps),Node(-eps,INF),0);
	sta[++tp]=Line(Node(-eps,INF),Node(-INF,INF),0);
	sta[++tp]=Line(Node(-INF,INF),Node(-INF,eps),0);
	std::sort(sta+1,sta+tp+1);
	rg int l=1,r=n,mids;
	while(l<=r){
		mids=(l+r)>>1;
		if(SI(mids)) l=mids+1;
		else r=mids-1;
	}
	printf("%d
",r);
	return 0;
}

二、Saber VS Lancer

题目传送门

分析

刘汝佳蓝书上的例题

设三个项目路程的长度分别为 (a,b,c)

如果 (i) 想要获胜，必须满足对于任意的 (j)都有

(frac{a}{v_i}+frac{b}{u_i}+frac{c}{w_i}<frac{a}{v_j}+frac{b}{u_j}+frac{c}{w_j})

这里面含有三个未知数 (a,b,c)，不是很好处理

但是如果 (a,b,c) 满足条件

那么 (2a,2b,2c) 肯定也满足条件

我们不需要关系它们的和，只需要保证它们的比例符合条件即可

所以可以设 (c=1-a-b)

那么就有 (frac{a}{v_i}+frac{b}{u_i}+frac{1-a-b}{w_i}<frac{a}{v_j}+frac{b}{u_j}+frac{1-a-b}{w_j})

((frac{1}{v_j}-frac{1}{w_j}-frac{1}{v_i}+frac{1}{w_i})a+(frac{1}{u_j}-frac{1}{w_j}-frac{1}{u_i}+frac{1}{w_i})+(frac{1}{w_j}-frac{1}{w_i})>0)

是一个半平面交的形式

但是只把这些直线加进去是不够的

我们还要保证 (x>0,y>0,x+y<1)

同时还要特判掉 (j) 三个项目的速度都比 (i) 慢和都比 (i) 快的情况

为了防止掉精，我把系数都乘了一个 (bas)

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=205;
const double eps=1e-12,INF=1e10,bas=1e5;
int dcmp(rg double now){
	return std::fabs(now)<=eps?0:(now>0?1:-1);
}
struct Node{
	double x,y;
	Node(){}
	Node(rg double aa,rg double bb){
		x=aa,y=bb;
	}
	friend Node operator -(rg const Node& A,rg const Node& B){
		return Node(A.x-B.x,A.y-B.y);
	}
	friend Node operator +(rg const Node& A,rg const Node& B){
		return Node(A.x+B.x,A.y+B.y);
	}
	friend Node operator *(rg const Node& A,rg const double& B){
		return Node(A.x*B,A.y*B);
	}
	friend Node operator /(rg const Node& A,rg const double& B){
		return Node(A.x/B,A.y/B);
	}
	friend double operator *(rg const Node& A,rg const Node& B){
		return A.x*B.x+A.y*B.y;
	}
	friend double operator ^(rg const Node& A,rg const Node& B){
		return A.x*B.y-B.x*A.y;
	}
	friend bool operator ==(rg const Node& A,rg const Node& B){
		return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;
	}
	double angle(){
		return atan2(y,x);
	}
}q2[maxn];
struct Line{
	Node s,t;
	double ang;
	Line (rg Node A=Node(),rg Node B=Node()){
		s=A,t=B,ang=(B-A).angle();
	}
	friend bool operator <(rg const Line& A,rg const Line& B){
		rg double r=A.ang-B.ang;
		if(dcmp(r)!=0) return dcmp(r)==-1;
		return dcmp((A.t-A.s)^(B.t-A.s))==-1;
	}
	friend double operator *(rg const Line& A,rg const Line& B){
		return (A.t-A.s)^(B.t-B.s);
	}
}sta[maxn],q1[maxn];
int tp=0,head,tail,n;
bool judline(rg Line aa,rg Line bb){
	return dcmp(aa*bb)==0;
}
bool onright(rg Line aa,rg Node bb){
	return dcmp((aa.t-aa.s)^(bb-aa.s))<0;
}
Node getsi(rg Line aa,rg Line bb){
	return aa.s+(aa.t-aa.s)*(((bb.t-bb.s)^(aa.s-bb.s))/((aa.t-aa.s)^(bb.t-bb.s)));
}
bool SI(){
	std::sort(sta+1,sta+tp+1);
	head=tail=0;
	q1[0]=sta[1];
	for(rg int i=2;i<=tp;i++){
		if(dcmp(sta[i].ang-sta[i-1].ang)!=0){
			if(head<tail && (judline(q1[head],q1[head+1]) || judline(q1[tail],q1[tail-1]))) return 0;
			while(head<tail && onright(sta[i],q2[tail-1])) tail--;
			while(head<tail && onright(sta[i],q2[head])) head++;
			q1[++tail]=sta[i];
			if(head<tail) q2[tail-1]=getsi(q1[tail],q1[tail-1]);
		}
	}
	while(head<tail && onright(q1[head],q2[tail-1])) tail--;
	while(head<tail && onright(q1[tail],q2[head])) head++;
	if(tail-head<=1) return 0;
	return 1;
}
int v[maxn],u[maxn],w[maxn];
int main(){
	n=read();
	for(rg int i=1;i<=n;i++){
		v[i]=read(),u[i]=read(),w[i]=read();
	}
	rg double A,B,C;
	for(rg int i=1;i<=n;i++){
		tp=0;
		rg bool jud=1;
		rg int jud1=0,jud2=0,jud3=0;
		for(rg int j=1;j<=n;j++){
			if(i==j) continue;
			if(v[i]<=v[j] && u[i]<=u[j] && w[i]<=w[j]){
				jud=0;
				break;
			}
			if(v[i]>=v[j] && u[i]>=u[j] && w[i]>=w[j]) continue;
			A=(bas/(double)v[j]-bas/(double)w[j])-(bas/(double)v[i]-bas/(double)w[i]);
			B=(bas/(double)u[j]-bas/(double)w[j])-(bas/(double)u[i]-bas/(double)w[i]);
			C=bas/(double)w[j]-bas/(double)w[i];
			jud1=dcmp(A),jud2=dcmp(B),jud3=dcmp(C);
			if(!jud1){
				if(!jud2){
					if(jud3<=0){
						jud=0;
						break;
					}
					continue;
				} else {
					sta[++tp]=Line(Node(0,-C/B),Node(jud2,-C/B));
				}
			} else {
				if(!jud2){
					sta[++tp]=Line(Node(-C/A,0),Node(-C/A,-jud1));
				} else {
					if(jud2>0) sta[++tp]=Line(Node(0,-C/B),Node(1,-A/B-C/B));
					else sta[++tp]=Line(Node(1,-A/B-C/B),Node(0,-C/B));
				}
			}
		}
		sta[++tp]=Line(Node(eps,eps),Node(eps,-1));
		sta[++tp]=Line(Node(eps,eps),Node(1,eps));
		sta[++tp]=Line(Node(1,eps),Node(eps,1));
		if(jud){
			if(SI()==0) jud=0;
		}
		if(jud) printf("Yes
");
		else printf("No
");
	}
	return 0;
}

三、P3297 [SDOI2013] 逃考

题目传送门

分析

对于两个亲戚来说，它们监视范围的分界线就是它们两点之间连线的中垂线

如果跨过这条线，那么就会多被一个亲戚监视

因此，我们可以在边界相邻的亲戚之间建一条边权为 (1) 的边

然后去跑最短路

起点就是一开始监视小杨的那个亲戚

关键在于如何求出哪两个亲戚边界是相邻的

因为 (n) 的范围比较小，我们可以对于每一个亲戚跑一次半平面交

求出这个亲戚和其它亲戚连线的中垂线

中垂线上记一个 (id) 代表它属于哪一个亲戚

然后把所有的中垂线扔到一起跑半平面交

最后和剩下的直线代表的亲戚连边即可

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=7e5+5;
const double eps=1e-10;
int dcmp(rg double now){
	return std::fabs(now)<=eps?0:(now>0?1:-1);
}
int t,n,zdx,zdy,qdx,qdy,h[maxn],tot=1,dis[maxn],s;
bool vis[maxn];
struct asd{
	int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	b[tot].val=cc;
	h[aa]=tot++;
}
struct Node{
	double x,y;
	Node(){}
	Node(rg double aa,rg double bb){
		x=aa,y=bb;
	}
	friend Node operator +(const Node& A,const Node& B){
		return Node(A.x+B.x,A.y+B.y);
	}
	friend Node operator -(const Node& A,const Node& B){
		return Node(A.x-B.x,A.y-B.y);
	}
	friend Node operator *(const Node& A,const double& B){
		return Node(A.x*B,A.y*B);
	}
	friend Node operator /(const Node& A,const double& B){
		return Node(A.x/B,A.y/B);
	}
	friend double operator ^(const Node& A,const Node& B){
		return A.x*B.y-B.x*A.y;
	}
	friend double operator *(const Node& A,const Node& B){
		return A.x*B.x+A.y*B.y;
	}
	double angle(){
		return atan2(y,x);
	}
}q2[maxn],a[maxn];
struct Line{
	Node s,t;
	int id;
	double ang;
	Line(rg Node A=Node(),rg Node B=Node(),rg int C=0){
		s=A,t=B,ang=(B-A).angle(),id=C;
	}
	friend bool operator <(const Line& A,const Line& B){
		double r=A.ang-B.ang;
		if(dcmp(r)==0) return dcmp((A.t-A.s)^(B.t-A.s))==-1;
		return dcmp(r)==-1;
	}
	friend double operator *(const Line& A,const Line& B){
		return (A.t-A.s)^(B.t-B.s);
	}
}sta[maxn],q1[maxn];
bool judline(rg Line aa,rg Line bb){
	return dcmp(aa*bb)==0;
}
bool onright(rg Line aa,rg Node bb){
	return dcmp((aa.t-aa.s)^(bb-aa.s))==-1;
}
Node getsi(rg Line aa,rg Line bb){
	return aa.s+(aa.t-aa.s)*(((bb.t-bb.s)^(aa.s-bb.s))/(aa*bb));
}
double getdis(rg Node aa,rg Node bb){
	return (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y);
}
int tp=0,head,tail;
void SI(rg int id){
	std::sort(sta+1,sta+tp+1);	
	head=tail=0;
	q1[0]=sta[1];
	for(rg int i=2;i<=tp;i++){
		if(dcmp(sta[i].ang-sta[i-1].ang)!=0){
			if(head<tail && (judline(q1[head],q1[head+1]) || judline(q1[tail],q1[tail-1]))) return;
			while(head<tail && onright(sta[i],q2[tail-1])) tail--;
			while(head<tail && onright(sta[i],q2[head])) head++;
			q1[++tail]=sta[i];
			if(head<tail) q2[tail-1]=getsi(q1[tail],q1[tail-1]);
		}
	}
	while(head<tail && onright(q1[head],q2[tail-1])) tail--;
	while(head<tail && onright(q1[tail],q2[head])) head++;
	if(tail-head<=1) return;
	q2[tail]=getsi(q1[head],q1[tail]);
	for(rg int i=head;i<=tail;i++){
		ad(id,q1[i].id,(q1[i].id<=n)?1:0);
	}
}
struct jie{
	int num,dis;
	jie(){}
	jie(rg int aa,rg int bb){
		num=aa,dis=bb;
	}
	bool operator <(const jie& A)const{
		return dis>A.dis;
	}
};
std::priority_queue<jie> q;
void dij(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=1;
	q.push(jie(s,dis[s]));
	while(!q.empty()){
		rg int now=q.top().num;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(rg int i=h[now];i!=-1;i=b[i].nxt){
			rg int u=b[i].to;
			if(dis[u]>dis[now]+b[i].val){
				dis[u]=dis[now]+b[i].val;
				q.push(jie(u,dis[u]));
			}
		}
	}
}
double mmax=1e18;
double xl(rg Node aa,rg Node bb){
	return (double)(bb.y-aa.y)/(bb.x-aa.x);
}
Line getmid(rg int i,rg int j){
	if(dcmp(a[i].x-a[j].x)==0){
		if(a[i].y<a[j].y) return Line(Node(0,(a[i].y+a[j].y)/2.0),Node(-1,(a[i].y+a[j].y)/2.0),j);
		else return Line(Node(0,(a[i].y+a[j].y)/2.0),Node(1,(a[i].y+a[j].y)/2.0),j);
	}
	if(dcmp(a[i].y-a[j].y)==0){
		if(a[i].x<a[j].x) return Line(Node((a[i].x+a[j].x)/2.0,-1),Node((a[i].x+a[j].x)/2.0,0),j);
		else return Line(Node((a[i].x+a[j].x)/2.0,1),Node((a[i].x+a[j].x)/2.0,0),j);
	}
	rg double nk=xl(a[i],a[j]);
	rg double nx=(a[i].x+a[j].x)/2.0,ny=(a[i].y+a[j].y)/2.0;
	nk=-1.0/nk;
	rg double nb=ny-nk*nx;
	if(a[i].y<a[j].y) return Line(Node(1,nk+nb),Node(0,nb),j);
	else return Line(Node(0,nb),Node(1,nk+nb),j);
}
int main(){
	t=read();
	while(t--){
		n=read(),zdx=read(),zdy=read(),qdx=read(),qdy=read();
		if(n==0){
			printf("0
");
			continue;
		}
		memset(h,-1,sizeof(h));
		tot=1,s=0,mmax=1e18;
		for(rg int i=1;i<=n;i++){
			a[i].x=read(),a[i].y=read();
		}
		for(rg int i=1;i<=n;i++){
			if(a[i].x<0 || a[i].x>zdx || a[i].y<0 || a[i].y>zdy) continue;
			if(getdis(Node(qdx,qdy),a[i])<mmax){
				mmax=getdis(Node(qdx,qdy),a[i]);
				s=i;
			}
		}
		for(rg int i=1;i<=n;i++){
			tp=0;
			if(a[i].x<0 || a[i].x>zdx || a[i].y<0 || a[i].y>zdy) continue;
			for(rg int j=1;j<=n;j++){
				if(a[j].x<0 || a[j].x>zdx || a[j].y<0 || a[j].y>zdy) continue;
				if(i==j) continue;
				sta[++tp]=getmid(i,j);
			}
			sta[++tp]=Line(Node(eps,eps),Node((double)zdx+eps,eps),n+1);
			sta[++tp]=Line(Node((double)zdx+eps,eps),Node((double)zdx+eps,(double)zdy+eps),n+1);
			sta[++tp]=Line(Node((double)zdx+eps,(double)zdy+eps),Node(eps,(double)zdy+eps),n+1);
			sta[++tp]=Line(Node(eps,(double)zdy+eps),Node(eps,eps),n+1);
			SI(i);
		}
		dij();
		printf("%d
",dis[n+1]);
	}
	return 0;
}