近日JZ对我说:"YXC最近水平有所长进,看他MAN SPACE里面贴了一个dijkstra+heap的程序."我惊讶,这个玩意儿我一直认为很烦(广大人民群众是这样说的..),没敢去涉足,没想到现在YXC都会了.JZ在2006年底就会了,汪一宁在去年联赛的时候就在宿舍和我说了.我认为虽然SPFA很强大,但是dijk+heap也是应该会的,于是当天下午就去看,感觉还是满简单的嘛,就是被"人民群众"的呼声吓住了.

于是昨天找题目练习,没相想到VIJOS上面只有一个合适的题目,居然还要做计算几何,就和我上次AC的CTSC的那个CUPID的题是一样的,但这次的计算几何相当的烦,核心是:已知地球半径(当作标准的球),地球表面两个点A,B分别的经纬度坐标,计算地球表面上A到B的最短路线长度(曲线).明摆的一个地理(我居然还记得..)+立体几何的计算当然我最后还是决定迎难而上,开始推算我从来没算过的立体几何公式

Program Vijos_1050_Csy;Uses Math;Const Maxn=11000; Maxm=101000; Pi=3.14
15926535897
93238462643383279; R=6374;Type Vex=record a,b,ef,er:longint; x,y,z:double; ew,ns:char end;Var v:array[1..maxn]of vex; h,p:array[1..maxn]of longint; dist:array[1..maxn]of double; used:array[1..maxn]of boolean; edge,next:array[0..maxm]of longint; leng:array[0..maxm]of double; n,st:longint;Function Distance(x,y:longint):double; var d:double; begin d:=sqrt(sqr(v[x].x-v[y].x)+sqr(v[x].y-v[y].y)+sqr(v[x].z-v[y].z)); distance:=2*r*arcsin(d/2/r) end;Procedure First;var i,m,x,a,b:longint; ch:char; procedure getxyz(i:longint); begin with v[i] do begin x:=r*cos(a*pi/180)*sin(b*pi/180); if ew='W' then x:=-x; y:=r*sin(a*pi/180); if ns='S' then y:=-y; z:=-r*cos(a*pi/180)*cos(b*pi/180) end end;beginreadln(n);for i:=1 to n do begin x:=0;read(ch); while ch in ['0'..'9'] do begin x:=10*x+ord(ch)-48;read(ch) end; v[i].b:=x;v[i].ew:=ch;read(ch); //blank x:=0;read(ch); while ch in ['0'..'9'] do begin x:=10*x+ord(ch)-48;read(ch) end; v[i].a:=x;v[i].ns:=ch; getxyz(i); v[i].ef:=0;v[i].er:=0; readln end;i:=0;while not eof do begin inc(i); readln(a,b); edge[i]:=b;leng[i]:=Distance(a,b);next[i]:=0; if v[a].ef=0 then v[a].ef:=i else next[v[a].er]:=i; v[a].er:=i; endend;Procedure Dijkstra_Heap;var u,t,x,i:longint; procedure swap(a,b:longint); var t:longint; begin p[h[a]]:=b;p[h[b]]:=a; t:=h[a];h[a]:=h[b];h[b]:=t end; procedure up(i:longint); var f:longint; begin if i>1 then begin f:=i div 2; if dist[h[f]]>dist[h[i]] then begin swap(f,i);up(f) end end end; procedure down(i:longint); var l,r:longint; begin l:=2*i;r:=l+1; if l<=n then if r<=n then if (dist[h[i]]>dist[h[l]])and(dist[h[l]]<=dist[h[r]]) then begin swap(i,l);down(l) end else if (dist[h[i]]>dist[h[r]])and(dist[h[r]]<=dist[h[l]]) then begin swap(i,r);down(r) end else if dist[h[i]]>dist[h[l]] then swap(i,l) end;beginst:=n;fillchar(used,sizeof(used),0);dist[1]:=0;for i:=2 to n do dist[i]:=1e50;for i:=1 to n do begin h[i]:=i;p[i]:=i end;for i:=(n div 2) downto 1 do down(i);while n>1 do begin u:=h[1];used[u]:=true; t:=v[u].ef; while t<>0 do begin x:=edge[t]; if not used[x] and (dist[x]>dist[u]+leng[t]) then begin dist[x]:=dist[u]+leng[t];up(p[x]) end; t:=next[t]; end; h[1]:=h[n];dec(n);down(1); if u=st then n:=1 end;end;Procedure Finish;beginif dist[st]<1e40 then writeln(dist[st]:0:2) else writeln('Impossible')end;BeginFirst;Dijkstra_Heap;FinishEnd.

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 88ms├ 测试数据 10：答案正确... 72ms-------------------------Accepted 有效得分：100 有效耗时：160ms嗯..速度果然很快..这个题真综合性真是强啊,地理,立体几何,数据结构(就是HEAP啦),图论算法,全齐了.本人才初三,搞那个立体的计算几何很不容易的,辛苦.第一次写DIJKSTRA+HEAP,练习一下,成功但是居然神奇地一次提交就过了,其实很成功的,但是实在是感觉没有成就感,因为没有WA很多次经过不懈努力才AC的爽的感觉...那个才叫爽,才叫释放

其实立体几何可以转化为平面几何解决的嘛...这个题目的可以错的地方太多了,我编的时候都有点晕了但却一次就AC,大部分在于运气好,小部分在于,我现在对程序和算法的实现能力也有所提高了

早就说过这个吧就是CSY的自恋吧～～

如果是我的博客你就不会这么说了吧但我就是把帖吧当BLOG的..

这个是所有OIer的习惯,太正常不过了.你去看他们的BLOG,全都充斥着题目啊,训练日记啊之类的东西..

YY的没有。ZYT的没有。HX没有BLOG。SZA好像也没有写这些。只有YXC和那个神经有点问题的和你一样。写了爆多的题目。反正从来都当YXC有病的。

才写几个字啊,可能他们还没进入正题呢,,,可能有人对OI感情不深吧..说明我和YXC钟情OI(虽然我的物理和数学也很强),ZYT他们将来就想在NOIP(联赛)里面混混,主攻数学的,当然不会有什么感情.当然我主攻3门竞赛,哈哈看看OI大牛们的BLOG,当然都是关于OI的内容,可以当书读的P.S.网络上最有名的YY是安徽的国家队大牛,JLHS的也YY我差一点看不懂

哈哈哈哈……为了你CSY单独注册的一个马甲～

您好象不太友好.1,我早就知道您会无聊,所以很谨慎地说的是"ZYT他们",不要没事找事做2,您想骂人就骂出来吧,还"有病哦?!",打个感叹号吓哪个啊3,无回复4,有人比我强不是很正常嘛,但是反正不是JLHS的您的好朋友们. 什么奋斗史,我历史记录不好,但这个不能说明现在和未来的问题5,您干什么我管不了6,您凭什么警告,您什么身份?为什么总是抬高JLHS的人,贬低我?您就总认为他们高我一等?您这样我就无法和您交流了

……发现你和一个人有一样的通病。你们可能太在乎一些东西了。而我却很不幸的触碰到了。你和他当初做的事情如出一辙。其实，有时候，何必如此的在意。如果我说我在开玩笑，你怎样？你似乎一点都不习惯于我们正常的玩笑话。更不用说带点恶搞的了。我承认啊，我最近被省招的人压的透不过气啊。。。至于你要的试卷，我也是个学生。我也有我自己的课业。何况我才培训完。而且，我最近生病了，请了6天的假，都没缓过来。在承担那样一份试卷和分析作业，我受不了。我物理最近遇到麻烦了，缺课太多。所以，我很忙。试卷嘛，因为考虑到本来你还有一个暑假的。我已经打算录入到电脑了。你如果真的很需要，要我快点，我完全可以加班加点给你录入。我不在乎再失眠几天。我没恶意，希望你相信。可能有些人天生就性格不合罢。

你要的东西在你信箱里。登陆MSN就看到了。

啊,我昨天真可怕...不好意思啊,太冲动了以后我一定要大度一点,理智一点

呵呵。没事了。你太在乎一些完全没必要在乎的东西。看开点。活的要开心才行。不然，就是对不起自己人生在世吃的那么多苦。不划得来啊～～