31 条题解

  • 1
    @ 2020-10-31 10:51:06

    思路一:朴素想法,在所有切点间暴力建边对于每一个询问顺时针逆时针交替搜索。

    时间复杂度:\(O(玄学)\)

    思路二:不难发现此题的每组询问之间有且仅有两条路径,
    且这两条路径之和为路径上所有经过的圆的周长之和。

    于是想到求出任意一条路径
    ,然后使用路径上所有经过的圆的周长之和减去这条路径的长度得到另一条路径长度,再比较大小。

    将每个圆看作一个点,两圆相切则连边,不难看出这是一棵树。

    将最大的圆代表的点看做根节点,
    则其实一条路径上所有经过的圆就是这两个点的LCA所经过的点代表的圆,
    所以我们可以通过LCA求路径的方式快速求出使用路径上所有经过的圆的周长之和。

    然后再进一步,
    其实两点间路径也可以通过类似的方式
    (比如定义一个标准方向,即在深度为偶数的圆上顺时针走,
    深度为奇数的圆上顺时针走)。

    然后就可以发现其实一条路径可以分为五部分,
    即在询问中一个给定的节点(圆)由给定幅角到与它父亲节点(圆)的切点按照标准方向走的路径、
    这个给定的节点(圆)与它父亲节点(圆)的切点到给定的两个节点的LCA(圆)按照标准方向走的路径、
    在给定的两个节点的LCA(圆)上按照标准方向走的路径,
    另一个给定的节点(圆)与它父亲节点(圆)的切点到给定的两个节点的LCA(圆)按照逆标准方向走的路径、
    这个给定的节点(圆)由给定幅角到与它父亲节点(圆)的切点按照逆标准方向走的路径。

    可能上一段看起来有点冗长,则咱们来看点直观的:

    箭头代表这个圆的标准方向,则从\(A\)点到\(B\)点的路径可以分为五段,即红段、橙段、黄段、绿段(你没看错那就是一个点),蓝段。

    然后得到答案就很简单啦。

    但是注意还有两种情况,即一个圆是另一个圆父亲的情况或在同一圆上的情况,需单独考虑,由于比较简单,留给读者自己思考~~其实是我懒。~~

    下面上我冗长的代码(含注释)

    #include<bits/stdc++.h>
    using namespace std;
    const double pi=3.14159265358979323846;
    int nex[6005],beg[6005],to[6005],r[3005],n,m,t,e,s,ee[3005];
    struct T{
        double x,y,sonf[15],faf,wtcl;
        int d,fa[25],sn,snn,son[15];
    }tree[3005];//定义节点,sonf、faf为儿子节点(圆)、父亲节点(圆)的幅角
    void add(int x,int y){
        to[++e]=y;
        nex[e]=beg[x];
        beg[x]=e;
    }//链式前向星
    double dist(int d,double x,double y){
        if(x>y)return (2*pi-x+y)*r[d];
        return (y-x)*r[d];
    }//计算两点在尺寸为d的圆上逆时针距离
    void dfs(int s){
        for(int i=1;(1<<i)<=tree[s].d;i++)
            tree[s].fa[i]=tree[tree[s].fa[i-1]].fa[i-1];
        for(int i=beg[s];i;i=nex[i])dfs(to[i]);
    }//倍增预处理
    void dfs2(int s){
        for(int i=1;i<=tree[s].sn;i++)
            if(tree[s].d%2==0){ 
                tree[tree[s].son[i]].wtcl=
                    tree[s].wtcl+dist(tree[s].d,tree[s].sonf[i],tree[s].faf);
                dfs2(tree[s].son[i]);
            }
            else {
            tree[tree[s].son[i]].wtcl=
                tree[s].wtcl+dist(tree[s].d,tree[s].faf,tree[s].sonf[i]);
                dfs2(tree[s].son[i]);
            }
    }//标准方向的距离预处理
    int lca(int a,int b){
        if(tree[a].d>tree[b].d)
            swap(a,b);
        for(int i=20;i>=0;i--)
            if(tree[a].d+(1<<i)<=tree[b].d)
                b=tree[b].fa[i];
        if(a==b)return -1;
        for(int i=20;i>=0;i--)
            if(tree[a].fa[i]!=tree[b].fa[i]){
                a=tree[a].fa[i];
                b=tree[b].fa[i];
            }
        return tree[a].fa[0];
    }//LCA
    int main(){
        scanf("%d%d%d",&n,&m,&t);
        r[0]=1e5;
        ee[0]=1e5;//ee是r的前缀和
        for(int i=1;i<=n;i++)
            scanf("%d",&r[i]),ee[i]=ee[i-1]+r[i];
        s=1;//根节点为1
        for(int i=1;i<=m;i++){
            scanf("%lf%lf%d%d",&tree[i].x,&tree[i].y,&tree[i].d,&tree[i].fa[0]);
            //其实尺寸就相当于深度
            tree[tree[i].fa[0]].son[++tree[tree[i].fa[0]].sn]=i;//记录儿子
            add(tree[i].fa[0],i);//加边
        }
        for(int i=2;i<=m;i++){
            tree[tree[i].fa[0]].snn++;
            if(tree[i].x==tree[tree[i].fa[0]].x){
                if(tree[i].y>tree[tree[i].fa[0]].y)
                    tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi/2;
                else tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=3*pi/2;
            }
            else{
                if(tree[i].x>tree[tree[i].fa[0]].x&&
                    tree[i].y>=tree[tree[i].fa[0]].y)
                    tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                    atan((tree[i].y-tree[tree[i].fa[0]].y)/
                             (tree[i].x-tree[tree[i].fa[0]].x));
                if(tree[i].x<tree[tree[i].fa[0]].x&&
                    tree[i].y>=tree[tree[i].fa[0]].y)
                    tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                    pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                    (tree[i].x-tree[tree[i].fa[0]].x));
                if(tree[i].x<tree[tree[i].fa[0]].x&&
                    tree[i].y<tree[tree[i].fa[0]].y)
                    tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                    pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                    (tree[i].x-tree[tree[i].fa[0]].x));
                if(tree[i].x>tree[tree[i].fa[0]].x&&
                    tree[i].y<tree[tree[i].fa[0]].y)
                    tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=
                    2*pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/
                                        (tree[i].x-tree[tree[i].fa[0]].x));
            }//分四个区域和平行于x轴的两种情况讨论幅角
        }//求出sonf
        for(int i=1;i<=m;i++)
            for(int j=1;j<=tree[i].sn;j++){
                if(tree[i].x==tree[tree[i].son[j]].x){
                    if(tree[i].y>tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi/2;
                    else tree[tree[i].son[j]].faf=3*pi/2;
                }
                else{
                    if(tree[i].x>tree[tree[i].son[j]].x&&
                        tree[i].y>=tree[tree[i].son[j]].y)
                        tree[tree[i].son[j]].faf=
                        atan((tree[i].y-tree[tree[i].son[j]].y)/
                                 (tree[i].x-tree[tree[i].son[j]].x));
                    if(tree[i].x<tree[tree[i].son[j]].x&&
                        tree[i].y>=tree[tree[i].son[j]].y)
                        tree[tree[i].son[j]].faf=
                        pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                                        (tree[i].x-tree[tree[i].son[j]].x));
                    if(tree[i].x<tree[tree[i].son[j]].x&&
                        tree[i].y<tree[tree[i].son[j]].y)
                        tree[tree[i].son[j]].faf=
                        pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                                        (tree[i].x-tree[tree[i].son[j]].x));
                    if(tree[i].x>tree[tree[i].son[j]].x&&
                         tree[i].y<tree[tree[i].son[j]].y)
                        tree[tree[i].son[j]].faf=
                        2*pi+atan((tree[i].y-tree[tree[i].son[j]].y)/
                                (tree[i].x-tree[tree[i].son[j]].x));
                }//分四个区域和平行于x轴的两种情况讨论幅角
        }//求出faf
        dfs(s);//倍增
        for(int i=1;i<=tree[1].sn;i++)
            dfs2(tree[1].son[i]);//求出标准方向上的距离
        while(t--){
            int x,y,xxx,yyy;
            double ans,xx,yy,xf,yf,xh,yh,xxxx,yyyy,hh;
            scanf("%d%lf%d%lf",&x,&xf,&y,&yf);
            if(x==y){
                printf("%.0lf\n",min(fabs(xf-yf),2*pi-fabs(xf-yf))*r[tree[x].d]/pi);
                continue;
            }//在同一圆上的情况
            int h=lca(x,y);//求LCA
            if(h==-1){
                ans=0;
                if(tree[x].d>tree[y].d)
                    swap(x,y),swap(xf,yf);
                int kk;
                for(int i=1;i<=tree[x].sn;i++)
                    if(lca(tree[x].son[i],y)==-1)kk=i;
                if(tree[x].d%2==0)ans+=dist(tree[x].d,tree[x].sonf[kk],xf);
                else ans+=dist(tree[x].d,xf,tree[x].sonf[kk]);
                if(tree[y].d%2==0)ans+=dist(tree[y].d,yf,tree[y].faf);
                else ans+=dist(tree[y].d,tree[y].faf,yf);
                ans+=tree[y].wtcl;
                ans-=tree[tree[x].son[kk]].wtcl;
                if(ans>pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d]))
                    ans=2*pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d])-ans;
                printf("%.0lf\n",ans/pi);
                continue;
            }//“直系血亲”的情况
            for(int i=1;i<=tree[h].sn;i++){
                if(lca(tree[h].son[i],x)==-1)xxx=tree[h].son[i],
                xxxx=tree[h].sonf[i];
                if(lca(tree[h].son[i],y)==-1)yyy=tree[h].son[i],
                yyyy=tree[h].sonf[i];
            }
            if(tree[x].d%2==0)xx=dist(tree[x].d,xf,tree[x].faf);
            else xx=dist(tree[x].d,tree[x].faf,xf);
            if(tree[y].d%2==0)yy=dist(tree[y].d,tree[y].faf,yf);
            else yy=dist(tree[y].d,yf,tree[y].faf);
            xh=tree[x].wtcl-tree[xxx].wtcl;
            yh=2*pi*(ee[tree[y].d-1]-ee[tree[h].d])-(tree[y].wtcl-tree[yyy].wtcl);
            if(tree[h].d%2==0)hh=dist(tree[h].d,xxxx,yyyy);
            else hh=dist(tree[h].d,yyyy,xxxx);
            ans=xh+yh+xx+yy+hh;
            //分五段求和
            if
                (ans>pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1]))
                ans=2*pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1])-ans;
            //最后再比较大小
            printf("%.0lf\n",ans/pi);//输出
        }
        return 0;
    }
    
  • 0
    @ 2009-11-07 16:34:26

    Accepted 有效得分:100 有效耗时:222ms(时间很2)

    一个沙茶错误调了好久啊...

    顺便OTL一下LX

  • 0
    @ 2009-11-05 20:15:06

    半个星期的成果啊!

    先是在处理光滑路径上出了问题,卡了好久好久。

    处理完计算几何问题以后,本来以为只要线段树就可以的,但是发现TLE了。又只好改成ST表来做。

    其实这个题目就是考验耐心。。。8.46KB的程序,能称的上算法的只有ST表了。

  • 0
    @ 2009-02-21 20:29:51

    哪个BT出的题,站出来,小心我夺走你的初吻!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  • 0
    @ 2009-06-17 19:57:13

    update in June, 2009:

    回复cbtcs:

    虽然看起来我好象从开始交到AC用了一天。但是看清楚,我11-3号已经过了,后面只是优化代码而已!而且我们学校不像你们的,我们没有停课集训,那一天只是利用晚上晚自习的时间做而已!!

    ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

    难度为5,通过6人,通过率1/50的题目也不过如此嘛……就这样一下子就被我ac了。

    不过就是LCA+树的遍历+节点标号+RMQ+两个ST表+动态规划+记忆化搜索+位运算+计算几何+三角函数+反三角函数而已嘛…………

    Easy_dla. Pass!

  • 0
    @ 2008-09-30 14:10:34

    恐怖...

  • 0
    @ 2008-09-13 11:04:15

    在是人做的题吗?超BT啊!!!!!!!!!!!!

  • 0
    @ 2007-11-15 14:05:32

    LCA...偶的算法目前ok,只是要用80mb内存……哎,可恶的mle……

  • 0
    @ 2007-11-13 15:49:11

    强`发现这题时只有2人做了。。一个是站长

    一个是国家队大牛郭华阳

  • 0
    @ 2007-10-22 21:42:52

    这还是程序吗?

  • 0
    @ 2007-10-04 17:34:01

    什么什么哦?????不懂!!!??

  • 0
    @ 2007-09-26 16:18:24

    。。BT题

  • 0
    @ 2007-11-03 17:50:21

    Tarjan

    LCA问题的

    offline-algorithm.的改变式算法吧?

  • 0
    @ 2007-07-23 20:31:49

    有哪位大牛通过了,帮忙贴一下

  • 0
    @ 2007-07-23 13:55:38

    疯子,那人打好,有事不?不会进医院了吧!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  • 0
    @ 2007-11-13 14:22:10

    好象还有“小塔”的程序啊!!!!

    竟误导别人!

  • -1
    @ 2015-09-20 21:10:02

    cout<<i<<endl;

  • -1
    @ 2014-09-08 11:41:07

    不明觉厉~

  • -1
    @ 2012-08-19 17:21:36

    Const maxn=1000100;

    Var

    sa,sb,se,a,b,e,f,q:array[1..maxn*2]of int64;

    vis:array[1..maxn*2]of boolean;

    dis:array[1..maxn*2]of int64;

    n,m,k,i,j:longint;

    sum:qword;

    Procedure init;

    var i:longint;

    begin

    readln(n,m);

    for i:=1 to m do readln(sa[i],sb[i],se[i]);

    end;

    Procedure qsort(l,r:longint);

    var i,j,x,y:longint;

    begin

    i:=l;j:=r;x:=a[(l+r)shr 1];

    Repeat

    while a[i]x do dec(j);

    if ij;

    if idis+cost1[k] then begin

    dis[toti1[k]]:=dis+cost1[k];

    if not check[toti1[k]] then begin

    inc(tail);

    team[tail]:=toti1[k];

    check[toti1[k]]:=true;

    end;

    end;

    k:=next1[k];

    end;

    until head>tail;

    for i:=1 to p do inc(ans,dis[i]);

    end;

    procedure spfa2;

    var

    i,head,tail,k,u:longint;

    begin

    fillchar(check,sizeof(check),false);

    for i:=1 to p do dis[i]:=30000000001;

    head:=0;

    tail:=1;

    dis[1]:=0;

    team[1]:=1;

    check[1]:=true;

    repeat

    inc(head);

    u:=team[head];

    check:=false;

    k:=list2;

    while k0 do begin

    if dis[toti2[k]]>dis+cost2[k] then begin

    dis[toti2[k]]:=dis+cost2[k];

    if not check[toti2[k]] then begin

    inc(tail);

    team[tail]:=toti2[k];

    check[toti2[k]]:=true;

    end;

    end;

    k:=next2[k];

    end;

    until head>tail;

    for i:=1 to p do inc(ans,dis[i]);

    end;

    begin

    assign(input,'poj1511.in');

    reset(input);

    readln(nn);

    for ii:=1 to nn do begin

    readln(p,q);

    ans:=0;

    tot:=0;

    fillchar(list1,sizeof(list1),0);

    fillchar(list2,sizeof(list2),0);

    for i:=1 to q do begin

    readln(x,y,z);

    add1(x,y,z);

    add2(y,x,z);

    end;

    spfa1;

    spfa2;

    writeln(ans);

    end;

    close(input);

    end.

    Const maxn=1000100;

    Var

    sa,sb,se,a,b,e,f,q:array[1..maxn*2]of int64;

    vis:array[1..maxn*2]of boolean;

    dis:array[1..maxn*2]of int64;

    n,m,k,i,j:longint;

    sum:qword;

    Procedure init;

    var i:longint;

    begin

    readln(n,m);

    for i:=1 to m do readln(sa[i],sb[i],se[i]);

    end;

    Procedure qsort(l,r:longint);

    var i,j,x,y:longint;

    begin

    i:=l;j:=r;x:=a[(l+r)shr 1];

    Repeat

    while a[i]x do dec(j);

    if ij;

    if i

  • -1
    @ 2012-07-20 19:45:27

    终于知道这题为什么过的人那么少的原因了

    • @ 2016-10-06 18:54:55

      这题就是要有耐心,不难。奥数题比这些难多了。赞一下过的人!

信息

ID
1086
难度
9
分类
计算几何 点击显示
标签
递交数
468
已通过
27
通过率
6%
被复制
2
上传者