[BZOJ3199][SDOI2013]escape：半平面交

分析

好像叫V图什么的。

容易发现，对于每个点，其监视的范围就是这个点与其它所有点的垂直平分线分割平面后的半平面交。由于数据范围很小，所以我们可以直接枚举每个点，使用双端队列求出其监视的范围。若两个点的监视范围有公共边，那么就在这两个点之间连一条边，边权为\(1\)。然后从起点bfs一遍即可。

这里重点说一下求半平面交的细节，毕竟这是ErkkiErkko这个大菜鸡第一次写半平面交。

可以使用有向的直线，规定直线左侧的平面是合法的区域。

求两条有向直线的交点时，可以使用面积作为中间量进行转换，具体请参见代码。

如果两条直线方向相同，选更靠左的那一条，毕竟咱们求的是半平面交而不是半平面并，

说到半平面并，感觉可以通过高中数学里交补补并并补补交那套东西转化成半平面交来求解。

还有一个很重要的地方，因为是双端队列（或许也可以理解为，半平面交一般是围成一圈），所以在插入最后一条有向线段之后，要检查队尾两条直线的交点是否满足队首的直线，如果不满足就弹出队尾，直到满足为止。

半平面交进行极角排序的时候，直接用叉积来排的话会出很多奇奇怪怪的锅（因为叉积不满足偏序，大概吧，说错了不要喷ErkkiErkko，毕竟他这么菜），要用叉积的话必须分象限。还可以选择调用std::atan2()函数。这里最好预处理出来，而不要在cmp()函数中调用，否则会对常数有很大的影响（大概差\(7,8\)倍的样子，可怕）。

\(n\)对应的是横坐标不是纵坐标。

更具体的就看代码吧。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <queue>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=605;

int n,lcnt,hd,tl,ecnt,head[MAXN];

int s,dis[MAXN];

double R,C,sx,sy;

bool vis[MAXN],invalid[MAXN];

struct Edge{

	int to,nxt;

}e[MAXN*MAXN];

inline void add_edge(int bg,int ed){

	ecnt++;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

struct Po{

	double x,y;

	inline friend Po operator + (Po A,Po B){return (Po){A.x+B.x,A.y+B.y};}

	inline friend Po operator - (Po A,Po B){return (Po){A.x-B.x,A.y-B.y};}

	inline friend Po operator * (Po A,double B){return (Po){A.x*B,A.y*B};}

	inline friend Po operator / (Po A,double B){return (Po){A.x/B,A.y/B};}

}re[MAXN];

inline int dcmp(double A,double B){return fabs(A-B)<1e-8?0:((A>B)*2)-1;}

inline Po getmid(Po A,Po B){return (Po){(A.x+B.x)/2,(A.y+B.y)/2};}

typedef Po Ve;

inline double getlen(Ve A){return sqrt(A.x*A.x+A.y*A.y);}

inline double getcross(Ve A,Ve B){return A.x*B.y-A.y*B.x;}

inline Ve getnor(Ve A){return (Ve){-A.y,A.x}/getlen(A);}

struct Li{

	Po u;Ve v;int id;double ang;

	inline friend bool operator < (Li A,Li B){return dcmp(A.ang,B.ang)<0;}

	inline Po getp(double t){return u+v*t;}

}l[MAXN],que[MAXN];

inline Po getinter(Li A,Li B){return A.getp(getcross(B.v,A.u-B.u)/getcross(A.v,B.v));}

inline Li getpb(Po A,Po B,int id){return (Li){getmid(A,B),getnor(B-A),id,0};}

inline bool isleft(Po A,Li B){return dcmp(getcross(B.v,A-B.u),0)>0;}

inline void solve(int x){

	lcnt=0;

	l[++lcnt]=(Li){(Po){0,0},(Ve){1,0},n+1,0},l[lcnt].ang=std::atan2(l[lcnt].v.y,l[lcnt].v.x);

	l[++lcnt]=(Li){(Po){C,0},(Ve){0,1},n+1,0},l[lcnt].ang=std::atan2(l[lcnt].v.y,l[lcnt].v.x);

	l[++lcnt]=(Li){(Po){C,R},(Ve){-1,0},n+1,0},l[lcnt].ang=std::atan2(l[lcnt].v.y,l[lcnt].v.x);

	l[++lcnt]=(Li){(Po){0,R},(Ve){0,-1},n+1,0},l[lcnt].ang=std::atan2(l[lcnt].v.y,l[lcnt].v.x);

	rin(i,1,n) if(!invalid[i]) if(i!=x) l[++lcnt]=getpb(re[x],re[i],i),l[lcnt].ang=std::atan2(l[lcnt].v.y,l[lcnt].v.x);

	std::sort(l+1,l+lcnt+1);

	hd=1,tl=0;

	rin(i,1,lcnt){

		while(hd<tl&&!isleft(getinter(que[tl-1],que[tl]),l[i])) tl--;

		while(hd<tl&&!isleft(getinter(que[hd],que[hd+1]),l[i])) hd++;

		if(hd<=tl&&dcmp(getcross(l[i].v,que[tl].v),0)==0){

			if(isleft(l[i].u,que[tl])) que[tl]=l[i];

		}

		else que[++tl]=l[i];

	}

	while(hd<tl&&!isleft(getinter(que[tl-1],que[tl]),que[hd])) tl--;

	rin(i,hd,tl) add_edge(x,que[i].id);

}

std::queue<int> bfq;

inline void bfs(){

	memset(dis,0x3f,sizeof dis);

	memset(vis,0,sizeof vis);

	while(!bfq.empty()) bfq.pop();

	vis[s]=1,dis[s]=1,bfq.push(s);

	while(!bfq.empty()){

		int x=bfq.front();bfq.pop();

		trav(i,x){

			int ver=e[i].to;

			if(vis[ver]) continue;

			vis[ver]=1,dis[ver]=dis[x]+1;

			if(ver==n+1) return;

			bfq.push(ver);

		}

	}

}

int main(){

	int T=read();

	while(T--){

		s=0;

		ecnt=0;memset(head,0,sizeof head);

		memset(invalid,0,sizeof invalid);

		n=read();

		C=read(),R=read(),sx=read(),sy=read();

		if(n==0){printf("0\n");continue;}

		rin(i,1,n){

			re[i].x=read(),re[i].y=read();

			if(re[i].x>=C||re[i].y>=R) invalid[i]=1;

		}

		rin(i,1,n) if(!invalid[i]) solve(i);

		rin(i,1,n) if(!invalid[i]) if(!s||dcmp(getlen(re[i]-(Po){sx,sy}),getlen(re[s]-(Po){sx,sy}))<0) s=i;

		bfs();

		printf("%d\n",dis[n+1]-1);

	}

	return 0;

}

巴特西

[BZOJ3199][SDOI2013]escape：半平面交

分析

代码

最新文章

热门文章