Felicia

2007年8月25日

[计算几何]pku1389
     摘要: 题目给出 n 个矩形，要求它们的面积并。具体做法是离散化。先把 2n 个 x 坐标排序去重，然后再把所有水平线段（要记录是矩形上边还是下边）按 y 坐标排序。最后对于每一小段区间 (x[i], x[i + 1]) 扫描所有的水平线段，求出这些水平线段在小区间内覆盖的面积。总的时间复杂度是 O(n^2)。利用线段树，可以优化到 O(nlogn)。

  阅读全文
posted @ 2007-08-25 17:53 Felicia 阅读(429) | 评论 (0) | 编辑 收藏
 
[计算几何]pku1279
     摘要: 求多边形的核。用半平面交算法。

  阅读全文
posted @ 2007-08-25 15:56 Felicia 阅读(647) | 评论 (4) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia