洛谷P3297 [SDOI2013] 逃考 题解

题目链接：P3297 [SDOI2013] 逃考

题意：髙考又来了，对于不认真读书的小杨来讲，真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨……

小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota,他决定越狱！

假设小杨的家是个 $x_1\times y_1$ 的矩阵，左下角坐标为 $(0,0)$ ，右上角坐标为 $(x_1,y_1)$ 。小杨有 $n$ 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控：

也就是说假设小杨所在的位置是 $(3,3)$ ，亲戚A在 $(3,0)$ ， A距离小杨距离是 $3$；亲戚B在 $(6,7)$ ，则B距离小杨距离是 $5$ 。距离A<距离B，所以 $(3,3)$ 位置由A监控。

如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。

给出小杨的坐标 $(x_0,y_0)$ 。因为被发现的人数越少，越狱成功的机会越大，所以小杨需要你设计一条越狱路线到达矩形的边上，且被发现的人数最少。

ps:小杨走的方向是任意的，也就是说路线上的任意位置需要是实数。

保证一开始小杨只被一个亲戚监控着。

注：这题目题面和数据有点问题，要注意特判掉那些在矩形外面的点

鉴于数据可能改掉（那样我画的图就没用了），给出原来样例的第二个测试数据：

1
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11

本题解法：半平面交+最短路

注意到每个亲戚都有一个管辖的范围

因此我们可以把每个亲戚向与其管辖范围相邻的亲戚连一条边权为 $1$ 的边

然后从第一个监管小杨的亲戚那里跑一下最短路就好了

那么管辖范围怎么求呢？

注意到对于亲戚 $u,v$ ，当小杨从 $u$ 的管辖范围转移到 $v$ 的范围时

一定经过了一条分界线

这条分界线就是直线 $u-v$ 的中垂线（垂直平分线）

这样，每个亲戚的管辖范围就是他与所有其他亲戚的中垂线的半平面交

对于上面那个样例，我画了个图，（没画不合法的点）

（看在q779花了1个小时的分上，点个赞吧）

其实这个图形就是个泰森多边形（知道也没用）

那么这个题好像就没啥难度了啊

时间复杂度 $O(Qn^2\log n)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define INF 0x3f3f3f3f3f3f3f3f
#define lb lower_bound
#define N (int)(666)
int n,s,t;
double w,h;
// ---------------vct--------------------
const double eps=1e-15;
#define pf(x) ((x)*(x))
struct vct{double x,y;}lamb,p[N],in[N];
vct operator+(vct a,vct b){return {a.x+b.x,a.y+b.y};}
vct operator-(vct a,vct b){return {a.x-b.x,a.y-b.y};}
vct operator*(vct a,double b){return {a.x*b,a.y*b};}
vct operator/(vct a,double b){return {a.x/b,a.y/b};}
double cross(vct a,vct b){return a.x*b.y-a.y*b.x;}
double dot(vct a,vct b){return a.x*b.x+a.y*b.y;}
double len(vct a){return sqrt(pf(a.x)+pf(a.y));}
double dis(vct a,vct b){return len(a-b);}
vct rot(vct a){return {-a.y,a.x};}
int dcmp(double x){if(fabs(x)<=eps)return 0;return x>eps?1:-1;}
// ---------------line--------------------
struct line
{
    vct p,way;
    double k;
    int id;
    void mkline(vct a,vct b,int ID)
    {
        p=a;way=b;
        k=atan2(b.y,b.x);
        id=ID;
    }
    void mk(double x1,double y1,double x2,double y2,int ID)
        {mkline({x1,y1},{x2-x1,y2-y1},ID);}
}a[N];
vct intersect(line a,line b)
{
    double t=cross(b.way,a.p-b.p)/cross(a.way,b.way);
    return a.p+a.way*t;
}
line getmidline(vct a,vct b,int id)
{
    line t;
    t.mkline((a+b)/2,rot(b-a),id);
    return t;
}
// ---------------SSSP--------------------
struct dist{int u,dis;};
bool operator<(dist a,dist b){return a.dis>b.dis;}
struct Edge{int u,v,w,next;}e[(int)(8e5+15)];
priority_queue<dist> q;
int d[N],vis[N];
int head[N],pos=1;
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
int dijkstra()
{
    memset(vis,0,(n+15)*sizeof(int));
    memset(d,0x3f,(n+15)*sizeof(int));
    while(!q.empty())q.pop();
    d[s]=0;q.push({s,0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }
    // for(int i=0; i<=n+5; i++)
    //     cout << (d[i]==INF?-1:d[i]) << " \n"[i==n+5];
    return d[t];
}
int init(int k)
{
    int o=0;
    for(int i=1; i<=n; i++)
    {
        if(i==k)continue;
        a[++o]=getmidline(in[k],in[i],i);
    }
    // o=n-1
    a[++o].mk(-eps,-eps,w,-eps,0);
    a[++o].mk(w,-eps,w,h,0);
    a[++o].mk(w,h,-eps,h,0);
    a[++o].mk(-eps,h,-eps,-eps,0);
    // o=n-1+4=n+3
    return o;
}
// ---------------halfplane--------------------
bool onright(vct a,line b){return dcmp(cross(b.way,a-b.p))<0;}
bool operator<(line a,line b)
{
    int d=dcmp(a.k-b.k);
    if(d==0)return dcmp(cross(b.p-a.p,b.way))>0;
    return d<0;
}
int st,en;
line que[N];
int qc[N];
void proc(int k)
{
    int oo=0,o=0;
    for(int i=st; i<=en; i++)
        qc[++oo]=que[i].id;
    sort(qc+1,qc+1+oo);
    o=unique(qc+1,qc+1+oo)-qc-1;
    for(int i=1; i<=o; i++)
        addEdge(k,qc[i],1),
        addEdge(qc[i],k,1);
}
void halfplane(int k,int lcnt)
{
    int o=0;
    // cout << lcnt << endl;
    sort(a+1,a+1+lcnt);
    // cout << "q779 is very cute." << endl;
    for(int i=1; i<=lcnt; i++)
        if(i==1||dcmp(a[i].k-a[i-1].k))
            a[++o]=a[i];
    que[st=en=1]=a[1];
    for(int i=2; i<=o; i++)
    {
        while(st<en&&onright(p[en],a[i]))--en;
        while(st<en&&onright(p[st+1],a[i]))++st;
        que[++en]=a[i];
        if(st<en)p[en]=intersect(que[en-1],que[en]);
    }
    while(st<en&&onright(p[en],que[st]))--en;
    if(en-st<=1)return;
    p[st]=intersect(que[st],que[en]);
    proc(k);
    // cout << pos << endl;
}
void clear()
{
    pos=1;t=0;
    memset(head,0,sizeof(head));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int Q;
    cin >> Q;
    while(Q--)
    {
        clear();
        cin >> n;
        if(!n){cout << 0 << endl;continue;}
        cin >> w >> h >> lamb.x >> lamb.y;
        double len=INF;
        int tmp=0,o=0;
        for(int i=1; i<=n; i++)
        {
            double x,y;
            cin >> x >> y;
            if(x>w||x<0||y>h||y<0)continue;
            in[++o]={x,y};
            double now=dis(in[i],lamb);
            if(dcmp(len-now)>0)len=now,tmp=o;
        }
        n=o;s=tmp;
        // cout << o << endl;
        for(int i=1; i<=n; i++)
        {
            int lcnt=init(i);
            // cout << lcnt << endl;
            halfplane(i,lcnt);
            // cout << "i=" << i << ",";
            // for(int j=head[i]; j; j=e[j].next)
            //     cout << e[j].v << " ";
            // cout << endl;
        }
        cout << dijkstra() << endl;
    }
    return 0;
}