给定一个 的二维平面,初始均为白色,有 个关键点 ,对于每一个关键点选择一个方向,并将该方向上的所有网格涂成黑色。易得操作后白色部分一定是一个矩形,请最大化矩形周长。
Constraints
,
Solution
观察可以得到一个性质,答案矩形一定会经过直线 或 。两种情况可以用相同的方式处理出答案。
将坐标离散化后,枚举矩形的上下边界,可以直接计算出矩形的左右边界。考虑用线段树进行优化。左右各开一个单调栈,在维护单调栈时在线段树上进行区间加减即可。
Code
1 |
|
Living is do or die.
给定一个 W×H 的二维平面,初始均为白色,有 n 个关键点 (xi,yi) ,对于每一个关键点选择一个方向,并将该方向上的所有网格涂成黑色。易得操作后白色部分一定是一个矩形,请最大化矩形周长。
0≤n≤2⋅105 ,1≤w,h≤108
观察可以得到一个性质,答案矩形一定会经过直线 x=2W 或 y=2H 。两种情况可以用相同的方式处理出答案。
将坐标离散化后,枚举矩形的上下边界,可以直接计算出矩形的左右边界。考虑用线段树进行优化。左右各开一个单调栈,在维护单调栈时在线段树上进行区间加减即可。
1 | #include<cstdio> |