163 条题解
-
0
Ronice LV 3 @ 2006-11-16 11:53:52
极度同意 prophet
。。。算出周长，把最长边减掉……
好汗阿……
很简单的，因为是凸多边形，所以周长肯定是经过所有点回到原点的最短路径
-
0
要是真是那样的话。干脆这样认为。
那人进门时是从任意的地方出发，目的就是去找自己的最短路径。
所以，只要找到这个不规则的图形的周长然后再排除一条就行了。
那一条就是最长的。
由于原来是逆时针排的所以,瞬间题就太简单了.
证明都不需要了,直截画个图就知道了.
PS1：乱说的。嘿嘿！！！！
PS2:貌似样例有错...55.198
至少我是：
From xiaomengxian
新年趣事之红包 新年趣事 系列
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
xiaozhuhaha LV 6 @ 2006-10-27 08:32:28
最小生成树就能过!!!!!!!!!
汗~~~~~~~~~~~~~~~~~~~~~
注:人难道可以飞??????????走的路径是棵树!!!!!!!!
汗死~~~~~~~~~~~~~~~~~~~~~~~~~~~ -
0
From xiaomengxian
新年趣事之红包 新年趣事 系列编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms肯定不是最小生成树，但是……
-
0
zyffyz8002 LV 3 @ 2006-09-15 20:39:21
汗……
vijos上的题还真是…… -
0
梦幻的感觉啊！！难度4的题一次AC……（这题也忒。。。）
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
想通了,题目是要求一个凸包,并且点集本身就构成了一个凸多边形
这个时候可以证明凸包(删去最大的一条边)(以下所说凸包均以删除最大边)等价于最小生成树证明:
(充分性)
在凸包上任取一条边ab(非最大的)
则若删去ab,将把凸包分成两个部分,连接这两个部分最小的代价必然是ab
(否则原图不可能是一个凸包)
则凸包是原图的最小生成树(必要性)
最小生成树每次取距离最小的两个点相连
而凸包中无锐角(我们已删去了最大边)
故对任意相邻的边ab,bc 有ac>ab,ac>bc(依此推广到任意ab,cd,ad+bc>ab+cd)
即最小生成树的扩展方式满足凸包的纯粹性
从而最小生成树是原图的一个凸包综上我们证明了在平面图中,一个本身形成凸多边形的点集的凸包等价于它的最小生成树
事实上这也是增量法求凸包的思想...以上纯属瞎扯..............................!!
Ronice
LV 3
@ 2006-11-16 11:53:52
信息
- ID
- 1069
- 难度
- 6
- 分类
- 动态规划 点击显示
- 标签
- 递交数
- 2183
- 已通过
- 644
- 通过率
- 30%
- 被复制
- 12
- 上传者
-
xiaomengxian
