2022/04/22 做题记录

Phorni

后缀平衡树模版，开个线段树维护区间询问就行。

code: /code/2022.4.22/bz3682.cpp

[SCOI2007]最大土地面积

先求出凸包，凸包大小小于等于 2 时答案是 0 ，等于 3 时可以枚举剩下的一个点，然后用大三角形面积减去这个点与三条边构成的三角形面积最小的一个，否则四个点一定都在凸包上，可以枚举一个点 i ，然后设 u=i+1,j=i+2,v=i+3，不断把 j 增加，然后用旋转卡壳维护 u 和 v，于是每次把 (i,u,j) 构成的三角形和 (i,v,j) 构成的三角形面积相加得到四边形面积，取最大值即可。

code: /code/2022.4.22/P4166.cpp