2007年8月15日

[计算几何]pku3347

摘要: 先把矩形扩大 sqrt(2) 倍，转化为整点问题。然后逐个求出每个矩形的坐标。
对于每个矩形分别求出在它之上的矩形覆盖的区间大小 t1，和包括它本身以及在它之上的矩形覆盖的区间大小 t2
若 t1 == t2，则该矩形被遮盖。

阅读全文

posted @ 2007-08-15 21:37 Felicia 阅读(384) | 评论 (0) | 编辑收藏

[动态规划]pku3345

摘要: 建立一个虚点（权为无穷大），从它到每个入度为 0 的点都连一条边，然后做树型DP。
先递归算出子结点的 f 值，然后用背包的方法计算父结点的 f 值。

阅读全文

posted @ 2007-08-15 18:42 Felicia 阅读(608) | 评论 (0) | 编辑收藏

[计算几何]pku3334

摘要: 二分水面高度，然后求总水量（就是求多边形面积）

阅读全文

posted @ 2007-08-15 08:59 Felicia 阅读(444) | 评论 (1) | 编辑收藏