1.奶牛浴场
题意搬运：
John要在牛场钟建造一个大型浴场，但是这个大型浴场不能覆盖任何一个奶牛的产奶点，John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场要是一个矩形，要求所求浴场面积尽可能大
最大子矩形定义：在一个给定的矩形中有一些障碍点，要找出内部不包含任何障碍点的矩形
定义有效子矩形为内部不包含任何障碍点的矩形
定义极大子矩形为每条边都不能向外拓展的有效子矩形
定义最大子矩形为所有极大子矩形中面积最大的子矩形
在一个有障碍点的矩形中的最大子矩形一点是一个极大子矩形
算法思路：通过枚举所有的极大子矩形，找出最大子矩形
两个不同的算法
算法1： 算法2:
时间复杂度:O(S^2) 时间复杂度:O(NM)
空间复杂度:O（S） 空间复杂度O(S)
S为障碍点个数,NM为整个矩形
算法1：
从极大子矩形的性质入手.
一个有效子矩形是极大子矩形的条件是，轮廓覆盖了障碍点，或者子矩形轮廓与矩形轮廓重合
基本算法:
算法:枚举上下左右四个边界，然后判断组成的矩形是否是有效子矩形。
fu
原文：https://www.cnblogs.com/xzx-1228/p/11585181.html