[BZOJ 2300] [HAOI 2011] 防线修建

题意:只有删点与查询操作,动态地维护一个上凸包的周长。

首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。

维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。

Note:

  1. 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
  2. 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+

Reference:

https://erjiaqing.github.io/2014/04/14/bzoj2300/

代码如下:

继续阅读[BZOJ 2300] [HAOI 2011] 防线修建

BZOJ【2300】防线修建

描述

在第一象限中给出m个点,其中一共有3个点一定要保护,求最小凸包周长。

在这题中,河道相等于一条防线,于是题目就简化成了求最小上凸包。再看看数据,每次减掉一个要保护的点。我们可以从后往前看,先把没有被询问到的点做一次凸包,接着就可以把删除的点看做是加上去的点。比如把2 3 1 4点依次删除询问,可以看做刚开始一个点都没有,接着把4 1 3 2点依次加入。

所以我们只要先存心每次询问,从后往前做动态凸包即可。

至于动态凸包,由于有三个点一定要保护,于是对于每个新加入的点,找出与其相邻的点, 用叉积判断其是否最优,若不是,就可以将其两边的点删除,继续判断。

在这里,找于加入的点相邻的点可以用平衡树来维护,每次需要O(logn)的时间查找。

可以用自带的set来实现。

关于set,可以看这http://blog.csdn.net/sunshinewave/article/details/8068326

继续阅读BZOJ【2300】防线修建