xzy的悬线法题单

王知昆2003年[论文](http://www.doc88.com/p-907281104686.html)首次提出两种解决最大子矩阵问题的方法——一种为$O(s^2)$，另一种为$O(nm)$，其中$n,m$为矩阵大小，$s$为障碍点数 注意：下面提到的“悬线法”均为$O(nm)$的算法，$O(s^2)$的算法用“另一种悬线法”表示 下面是题单： ### 洛谷 - [P1387 最大正方形](https://www.luogu.com.cn/problem/P1387)：裸的悬线法 - [P1169 [ZJOI2007]棋盘制作](https://www.luogu.com.cn/problem/P1169)：裸的悬线法 - [P2701 [USACO5.3]巨大的牛棚Big Barn](https://www.luogu.com.cn/problem/P2701)：（不是很确定，可能是悬线法） - [P4147 玉蟾宫](https://www.luogu.com.cn/problem/P4147)：裸的悬线法 - [P1578 奶牛浴场](https://www.luogu.com.cn/problem/P1578)：另一种悬线法，普通悬线法过不去 - [P3474 [POI2008]KUP-Plot purchase](https://www.luogu.com.cn/problem/P3474)：裸的悬线法，坑点：输入的时候坐标是反的 - [P3117 [USACO15JAN]Cow Rectangles G](https://www.luogu.com.cn/problem/P3117)：二分+另一种悬线法 - [SP277 CTGAME - City Game](https://www.luogu.com.cn/problem/SP277)：裸的悬线法 - [UVA1330 City Game](https://www.luogu.com.cn/problem/UVA1330)：与SP277重题 - [P3331 [ZJOI2011]礼物](https://www.luogu.com.cn/problem/P3331)：悬线法+单调栈？ ### HDU - [Cut the cake](http://acm.hdu.edu.cn/showproblem.php?pid=4328) - [To my boyfriend](http://acm.hdu.edu.cn/showproblem.php?pid=6052)