题解 P2778 【[AHOI2016初中组]迷宫】

· · 题解

笔者的做法和下面几篇题解是一样的，在这里就不重复叙述了。这里介绍一下官方给出的做法。

题目分析

把平面上每一个区域看作一个结点，最外层没有边界的区域也看作一个结点。如果一个区域刚好被另外一个区域直接包含，则连边。构成的图上做最短路径即可以得到40~60的分数。

又发现，上述得到的图是树结构的，在树上预处理好任意两点的最近公共祖先，之后的询问可以线形完成，这便可以得到满分。

std

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Point
{
    ll x,y;
    Point(){}
    Point(ll _x,ll _y):x(_x),y(_y){}
    Point operator - (const Point &t)const
    {
        return Point(x-t.x,y-t.y);
    }
    ll len2()
    {
        return x*x+y*y;
    }
};
struct Circle
{
    Point o;
    ll r;
    Circle(){}
    Circle(Point _o,ll _r):o(_o),r(_r){}
    bool operator < (const Circle &t)const
    {
        return r<t.r;
    }
    bool contain(Point t)
    {
        return (t-o).len2()<r*r;
    }
}c[8005];
struct Edge
{
    int to,nxt;
}edge[8005];
int head[8005],tot;
void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}
void addedge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
int fa[8005],dep[8005];
void dfs(int u,int la)
{
    fa[u]=la;
    dep[u]=(la>=0 ? dep[la]+1 : 0);
    for(int i=head[u];~i;i=edge[i].nxt)
        dfs(edge[i].to,u);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld%lld%lld",&c[i].o.x,&c[i].o.y,&c[i].r);
    c[n++]=Circle(Point(0,0),200000000);
    sort(c,c+n);
    init();
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(c[j].contain(c[i].o))
            {
                addedge(j,i);
                break;
            }
    dfs(n-1,-1);
    int m;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int u[2];
        for(int j=0;j<2;j++)
        {
            Point p;
            scanf("%lld%lld",&p.x,&p.y);
            for(int k=0;k<n;k++)
                if(c[k].contain(p))
                {
                    u[j]=k;
                    break;
                }
        }
        int res=0;
        while(u[0]!=u[1])
        {
            if(dep[u[0]]>dep[u[1]])u[0]=fa[u[0]];
            else u[1]=fa[u[1]];
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

吐槽

这玩意又难写，常数又大（原题时限5s），不知道出题人怎么想到的。