呃，是奥赛，不是ACM……奥赛对程序运行效率有要求么？[/quote]
有，一般为1sec(基本上时间复杂度计算出来不超过10^8即可……)，不过不像ACM那样要求过完所有数据，而是过一组给一组的分…… [quote][b]引用第39楼[i]KOU_ZX[/i]于[i]2007-04-13 12:14[/i]发表的“”[/b]:
不错，两个公式都很正确。不过这题目的难点就在于如何选择路线，假如穷举的话，那么每个石柱的每个顶点到其他任何一个顶点都要算作一个路径，并且计算角度（这倒不难，算出个相对与坐标系的角度，到时候两个角度做加减法），当然，由于遮挡关系，有些路径会被剪裁掉，但是如何确定哪些路径被剪裁也是一个问题，或许图形学里的图形剪裁算法可以帮点忙。经过剪裁剩下的路径才能够拿来穷举，不过这样的路径可能还剩下很多，这样很可能会超时
呃，是奥赛，不是ACM……奥赛对程序运行效率有要求么？[/quote]
对计算机的速度要有信心。
路径剪裁用“线段相交”来做，当路径线段和任意一个障碍线段相交的时候就丢弃这条路径。
广度优先搜索不是穷举，复杂度是O(n) n为边数，速度不用担心。（最多20个障碍，每个障碍考虑4个点，加上起点和终点共82个点，边数最多 n(n-1)/2 = 3321，何况经过剪裁至少减少一半）
顺便问一下，这个1s的时间限制，不知道是对于什么样配置的机器而言的呢？
对了，还有一个麻烦的地方：两个柱子之间距离过小的情况，这个怎么判断 [quote][b]引用第26楼[i]zi.zi..[/i]于[i]2007-04-10 17:37[/i]发表的“”[/b]:
这帖子果然是可怕的东西……不过我认为修马一定使用了第三种方法“亲爱的，帮我把那个石头球放到祭坛中心去好么？”“小菜一碟，honey~”[/quote]
这个解法不错~ [s:19] 这定然是E搞吖！ [quote][b]引用第17楼[i]Gellidus[/i]于[i]2007-04-09 23:56[/i]发表的“”[/b]:
凯特林：提利昂干的
提利昂：提培尔干的
提培尔：不是我干的
乔弗里：不是我干的
经调查证实，四人中只有一个人说的是真话。
问：谁干的？.......[/quote]
这个么，很简单，提利昂和提培尔的话是自相矛盾的，必然一真一假
那么他俩之外的某人说的必定是假话…… 集体参拜老师殿 法师的头脑果然好用 [quote][b]引用第41楼[i]Gellidus[/i]于[i]2007-04-13 22:12[/i]发表的“”[/b]:
对计算机的速度要有信心。
路径剪裁用“线段相交”来做，当路径线段和任意一个障碍线段相交的时候就丢弃这条路径。
广度优先搜索不是穷举，复杂度是O(n) n为边数，速度不用担心。（最多20个障碍，每个障碍考虑4个点，加上起点和终点共82个点，边数最多 n(n-1)/2 = 3321，何况经过剪裁至少减少一半）
.......[/quote]
广度优先确实不是穷举，但是也要先有一个分支树才能搜索，得先构建一个图，然后求图上圆球起始位置所在点到祭坛中心所在点的最小路径，而且这个图是带权的，而要知道每条边的权就得计算每个石柱的每一个顶点到另外任意一个顶点的距离
页:
1
[2]