刚刚在做poj2528。想起来以前傲妹让我们写的那一道usaco题，两道题都是在平面【直线】上用矩形【线段】覆盖，最后计算有几个矩形【线段】没有被完全覆盖。

usaco那道题n只有1000，但是大家都被这种题目吓傻了纷纷去写线段树，写出来的效率还都是O(n^2logn)的。当时我写的O(nlogn)的扫描线线段树，没考虑一种特殊情况导致整个算法是错的，但是数据弱居然也有80分。现在想来这题的最优算法应该是nlogn的扫描线线段树，每个节点储存该线段当前的矩形及被当前矩形覆盖的最上矩形。

这算法效率是最优的但是写起来很麻烦。当时被傲妹给出的标程之短震惊了。

矩形切割的想法很简单，即矩形与矩形相交的并也可以分割为若干个矩形。用递归来写很方便。矩形切割的想法在一维上的实现，即线段切割，在线段树七题里莫诺瑞根那道题的效率比线段树还高。

矩形\线段切割的最坏效率O(n^2)，但是能导致这种最坏效率的数据需要手工构造，确实比较麻烦。出题人一般也不会蛋疼到去刻意卡这种算法吧。【跟spfa还能用的理由差不多

想起来很简单，但是判断相交那里有很多种情况要考虑，貌似比较麻烦。后来发现，排除掉相离的情况，剩下的情况比较少，用4条语句每次考虑一条边的相交情况即可。

poj2528用线段切割写起来只有25行，235MS1A。效率不怎么样但是确实短。