摘要: 动态规划总结 by Amber
阅读全文
摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
平面欧几里德最小生成树是经典问题,可以做到O(nlogn)。具体做法是先对平面点进行三角剖分,时间复杂度是O(nlogn),三角剖分的边就是可能的在最小生成树的边。因为是平面图,所以有O(n)条边,在其上应用 Kruscal 算法即可。
阅读全文
摘要: 漫谈扭结
阅读全文
摘要: 此问题可转化为求三角形垂心。我的做法是设垂心坐标为(x, y),然后利用垂直关系解方程。
阅读全文
摘要: Ubuntu 6.10 @ Dell XPS M1210 安装手记
阅读全文
摘要: 一首小诗……
阅读全文
摘要: 平面点的曼哈顿最小生成树
阅读全文
摘要: 简单计算几何,我的做法是列出所有可能的切法(一共18种),求最优值。
阅读全文
摘要: 构造所有的线段,然后枚举每对水平-竖直线段,求交点,然后计算四边形面积,求最大值。
阅读全文
摘要: 强烈推荐此题!
状态压缩DP的好题!
分析见内
阅读全文