Felicia

2007年9月13日

I Want A Wife
     摘要: :)

  阅读全文
posted @ 2007-09-13 14:17 Felicia 阅读(233) | 评论 (2) | 编辑 收藏
 
[计算几何]pku2079
     摘要: 先求凸包，然后再用旋转卡壳方法求解。
具体做法是枚举三角形的第一个点i，设j = i + 1，k = j + 1。然后做以下操作：
1.计算i，j，k构成的三角形面积a1和i，j，k + 1构成的三角形面积a2，如果a2 < a1，则进行下一步，否则k++，重复此步。
2.记录此时的三角形面积b，如果b < preb（就是上一个j对应的三角形面积）j++，转第一步，否则退出。
可以证明这个算法的复杂度为O(n2)。具体实现见代码。

  阅读全文
posted @ 2007-09-13 13:40 Felicia 阅读(840) | 评论 (0) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia