摘要: 很好的基础题，判断直线相交的情况。要注意精度。判断平行和重合时，用整数运算比较精确。剩下的事就是解出交点了。

  阅读全文      摘要: 朴素做法是 O(n^3) 的，超时。我的做法是枚举每个点，然后求其它点和它连线的斜率，再排序。这样就得到经过该点的直线最多能经过几个点。求个最大值就行了。复杂度是 O(n^2logn) 的。把排序换成 hash，可以优化到 O(n^2)。

  阅读全文      摘要: 应用平面图的欧拉定理：V + F - E = 2
两两线段求交，得到交点数 V，然后判断每个交点落在几条边上，如果一个点在一条边上，这条边就分裂成两条边，边数加 1。这样得到边数 E。最后直接用欧拉定理解得 F。

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

  阅读全文      摘要: 先求凸包，答案是凸包周长 + 2πl。因为简单多边形的转角是360度，所以加上一个圆的周长。

  阅读全文      摘要: 简单题，直接模拟即可

  阅读全文      摘要: 公式很容易猜出，见代码

  阅读全文      摘要: pku 部分计算几何题目列表

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

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

  阅读全文