P3297 [SDOI2013]逃考
题意
给一个平面矩形，里面有一些有标号点，有一个是人物点，人物点会被最近的其他点控制，人物点要走出矩形，求人物点最少被几个点控制过。
保证一开始只被一个点控制，没有点在矩阵边界上
多组数据(tle 3)，点数(le600)。
画一画图可以发现
对每个点，这个点和另一个点的垂直平分线可以划分这两个点的控制区域，每个点搞出(n-1)个垂直平分线，然后加上边界的四条，做半平面交，然后对每个点向最后半平面交留下的线所代表的点连边，跑最短路就可以了，复杂度(O(n^2log 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
",dis[n+1]);
}
int main()
{
scanf("%d",&T);
while(T--) work();
return 0;
}
2019.2.11