【学术篇】luogu2778 [AHOI2016初中组]迷宫（代码高能！）

叁歲伎倆 2021-09-30 07:46 157阅读 0赞

**好久好久我都没有刷题了。**

题目の传送门：[https://www.luogu.org/problem/show?pid=2778][https_www.luogu.org_problem_show_pid_2778]

题目大意：（啥 题目讲得不够清楚？）平面内有n个以整点（就是坐标都是整数的点啦~）为圆心、互不相交或相切的圆，现给出q组询问，查询连接两个整点至少要跨过多少圆。

这题嘛，我们可以得出很显然的结论：  
1. 对于一个圆，如果A和B都不在圆内，则该圆可以被忽略。  
2. 对于一个圆，如果A和B都在圆内，则该圆可以被忽略。  
3. 一个圆被考虑，当且仅当AB二人中有且只有一人在圆内。

然后我们就可以乱搞了= =  
**我们对于每个询问，通过解析几何的公式暴力判断每个圆的求出点是否在圆内即可。**  
公式：

//设p为点，o为圆心
    dis(p,o)<=o.r
    dis(p,o)=sqrt(sqr(p.x-q.x)+sqr(p.y-q.y))

对 就这样 时间复杂度O(nq)，8000会卡（说好的大数据时限3s显然是tan(π/2)）  
所以交上去会TLE 4个点，这时候就要手动开O3了（微笑）

代码（呵呵，我就是故意的2333）：

QAQ ____{_w_ _,__,___;}OvO[o];QAQ ___{_w_ _,__;}OwO,O_O;_w_ w_v_w(___ _,____ __){w_w _(_._-__._)+_(_.__-__.__)<__.___;}
    _w_ main(){_w_ qwq,owo,TAT; _v_(qwq);_____(qwq){_v_(OvO[_]._);_v_(OvO[_].__);_v_(OvO[_].___);OvO[_].___*=OvO[_].___;}_v_(owo);_____(owo){TAT=ovo;_v_(OwO._);_v_(OwO.__); _v_(O_O._); _v_(O_O.__);_____(qwq)w_v_w(OwO,OvO[_])-w_v_w(O_O,OvO[_])?++TAT:ovo;v_v(TAT);}}

什么，你说你看不懂？  
给你加点必要的提示？

#define _(w) ((w)*(w))
    #define QAQ struct
    #define _w_ int
    #define w_w return
    #define orz main
    #define _v_(w) scanf("%d",&w);
    #define v_v(w) printf("%d\n",w);
    #define o 8008
    #define _____(v) for(int _=1;_<=v;_++)
    #define ovo 0

加起来就是这样

#include <cstdio>
    #define _(w) ((w)*(w))
    #define QAQ struct
    #define _w_ int
    #define w_w return
    #define orz main
    #define _v_(w) scanf("%d",&w);
    #define v_v(w) printf("%d\n",w);
    #define o 8008
    #define _____(v) for(int _=1;_<=v;_++)
    #define ovo 0
    QAQ ____{_w_ _,__,___;}OvO[o];QAQ ___{_w_ _,__;}OwO,O_O;_w_ w_v_w(___ _,____ __){w_w _(_._-__._)+_(_.__-__.__)<__.___;}
    _w_ main(){_w_ qwq,owo,TAT; _v_(qwq);_____(qwq){_v_(OvO[_]._);_v_(OvO[_].__);_v_(OvO[_].___);OvO[_].___*=OvO[_].___;}_v_(owo);_____(owo){TAT=ovo;_v_(OwO._);_v_(OwO.__); _v_(O_O._); _v_(O_O.__);_____(qwq)w_v_w(OwO,OvO[_])-w_v_w(O_O,OvO[_])?++TAT:ovo;v_v(TAT);}}

什么，你说你还看不懂，算了我给你翻译一下吧（其实上面就是抖个机灵，不过我就是这么交的2333）。。

#include <cstdio>
    #define sqr(a) ((a)*(a))
    struct circle{
        int x,y,r;
    }cir[8008];
    struct zb{
        int x,y;
    }a,b;
    int judge(zb u,circle v){
        return sqr(u.x-v.x)+sqr(u.y-v.y)<v.r; //这里的r是自乘过的（后面的处理），所以没有平方
    }i
    
    int main(){
        int q,n,s; scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r);
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            s=0;
            scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
            for(int j=1;j<=n;j++){ //好吧其实我也不知道刚才玄学代码里面循环变量一样是怎么A掉的
                if(judge(a,cir[j])==judge(b,cir[j]));
                    else s++; //上面的玄学代码用三目运算符就是记这么写的……
            }
            printf("%d\n",s);
        }
    }

嗯 就是这样= =  
哦 题解里面还有一个官方std解法（显然那才是玄学解法嘛）

转自luogu题解……  
作者: qq2477259579 更新时间: 2017-01-02 22:26

***把平面上每一个区域看作一个结点，最外层没有边界的区域也看作一个结点。如果一个区域刚好被另外一个区域直接包含，则连边。构成的图上做最短路径即可以得到40~60的分数。***  
***又发现，上述得到的图是树结构的，在树上预处理好任意两点的最近公共祖先，之后的询问可以线形完成，这便可以得到满分。***  
哇 代码你们自己去题解里找吧，我理解能力有限\_ (:з」∠) \_

我代码到底会不会写得更丑啊= =

转载于:https://www.cnblogs.com/enzymii/p/8412146.html

[https_www.luogu.org_problem_show_pid_2778]: https://www.luogu.org/problem/show?pid=2778