洛谷 P3297 [SDOI2013]逃考 解题报告

P3297 [SDOI2013]逃考

题意

给一个平面矩形，里面有一些有标号点，有一个是人物点，人物点会被最近的其他点控制，人物点要走出矩形，求人物点最少被几个点控制过。

保证一开始只被一个点控制，没有点在矩阵边界上

多组数据\(t\le 3\)，点数\(\le600\)。

---

画一画图可以发现

对每个点，这个点和另一个点的垂直平分线可以划分这两个点的控制区域，每个点搞出\(n-1\)个垂直平分线，然后加上边界的四条，做半平面交，然后对每个点向最后半平面交留下的线所代表的点连边，跑最短路就可以了，复杂度\(O(n^2\log n)\)

一些细节，交点坐标别瞎用fabs,要判平行

---

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

const int N=610;

const double eps=1e-6;

int head[N],to[N*N],Next[N*N],cnt;

void add(int u,int v){to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;}

#define Point Vector

struct Vector

{

	double x,y;

	Vector(){}

	Vector(double X,double Y){x=X,y=Y;}

	double angle(){return atan2(y,x);}

	Vector friend operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}

	Vector friend operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}

	Vector friend operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}

}q2[N],bee[N],yuy;

double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}

bool dcmp(double a,double b){return fabs(b-a)<eps;}

struct Line

{

	Point s,t;int id;double ang;

	Line(){}

	Line(Point S,Point T){s=S,t=T,ang=(t-s).angle();}

	bool friend operator <(Line a,Line b){return dcmp(a.ang,b.ang)?Cross(b.t-a.s,a.t-a.s)+eps>0:a.ang<b.ang;}

}Li[N],q1[N];

Point getmid(Point a,Point b){return Point((a.x+b.x)/2,(a.y+b.y)/2);}

Vector Rotate(Vector a){return Vector(a.y,-a.x);}

Line getl(Point a,Point b)

{

	Point c=getmid(a,b);

	return Line(c,c+Rotate(b-a));

}

Point jd(Line a,Line b){return b.s+(b.t-b.s)*(Cross(b.s-a.s,a.t-a.s)/Cross(a.t-a.s,b.t-b.s));}

bool isrig(Line a,Point b){return Cross(b-a.s,a.t-a.s)+eps>0;}

int ct,st;

void SI(int u)

{

	std::sort(Li+1,Li+1+ct);

	int l,r;

	q1[l=r=1]=Li[1];

	for(int i=2;i<=ct;i++)

	{

	    if(dcmp(Li[i].ang,Li[i-1].ang)) continue;

		while(l<r&&isrig(Li[i],q2[r-1])) --r;

		while(l<r&&isrig(Li[i],q2[l])) ++l;

		q2[r]=jd(Li[i],q1[r]);

		q1[++r]=Li[i];

	}

	while(l<r&&isrig(q1[l],q2[r-1])) --r;

	while(l<r&&isrig(q1[r],q2[l])) ++l;

	for(int i=l;i<=r;i++) add(u,q1[i].id);

	if(r-l<2) return;

	int flag=1;

	for(int i=l;i<=r;i++)

		if(isrig(q1[i],yuy))

            flag=0;

	if(flag) st=u;

}

double sx,sy;

int dis[N],used[N],n,T,q[N];

void init(int id)

{

	ct=0;Point d1=Point(0,0),d2=Point(sx,0),d3=Point(sx,sy),d4=Point(0,sy);

    Li[++ct]=Line(d1,d2),Li[++ct]=Line(d2,d3),Li[++ct]=Line(d3,d4),Li[++ct]=Line(d4,d1);

    for(int i=1;i<=4;i++) Li[i].id=n+1;

	for(int i=1;i<=n;i++)

		if(i!=id)

			Li[++ct]=getl(bee[i],bee[id]),Li[ct].id=i;

}

void work()

{

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

    scanf("%d",&n);

    scanf("%lf%lf%lf%lf",&sx,&sy,&yuy.x,&yuy.y);

    for(int i=1;i<=n;i++) scanf("%lf%lf",&bee[i].x,&bee[i].y);

    for(int i=1;i<=n;i++) init(i),SI(i);

    memset(dis,0,sizeof dis);

	memset(used,0,sizeof used);

	int l,r;

    used[q[l=r=1]=st]=1;

	while(l<=r)

	{

		int now=q[l++];

		for(int v,i=head[now];i;i=Next[i])

			if(!used[v=to[i]])

				used[q[++r]=v]=1,dis[v]=dis[now]+1;

	}

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

}

int main()

{

    scanf("%d",&T);

    while(T--) work();

    return 0;

}

---

2019.2.11