夜间模式
字体
阴影
滤镜
主题色
bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解

题意

在平面直角坐标系中有$n$个点,现在给你$3$个$L\times L$的正方形,问要用这$3$个正方形盖住所有点的最小的$L$。

思路

终于开始刷$bzoj$了$QwQ$...
非常明显,这道题肯定要二分,那么怎么写$check$呢?
可以考虑如果用一个非常大的正方形盖住了所有点,那么必定会有点在这个正方形的四条边上。所以有正方形必须在边上。但是只有$3$个小正方形,而大正方形有$4$条边,所以肯定有一个小正方形的两条边分别在大正方形的两条边上,换句话说就一定有一个小正方形在大正方形的一个角上。

大正方形围住所有点

大正方形围住所有点↑

3个小正方形

3个小正方形↑

那么$check$只需要枚举一下这个小正方形是在大正方形的哪一个角上即可。

Code

暂无评论

发送评论


				
上一篇
下一篇