[bzoj4570]-[SCOI2016]妖怪

狂补计算几何ing

题目(BZOJ)

题目(洛谷)

 

这题蛮卡常的……毕竟 $$n <= 10^6$$

来说说这题吧~

首先,我们可以用斜率 $$k$$ 来代替题目中的二元组 $$(a,b)$$,然后就可以计算啦.

我们不难发现,每个妖怪的最强战斗力值一定是过其直线的横截距与纵截距之和,我们的目的是让这个和最小. 同时也能发现,对答案有贡献的点一定在上凸壳上.

对于一个点 $$(x_i,y_i)$$,经过其直线的斜率为 $$k$$,那么这条直线方程为 $$y = kx + y_i – k x_i$$ ,那么其横截距为 $$\frac{k x_i – y_i}{k}$$,纵截距为 $$y_i – k x_i$$ .

可以发现对于一个点,经过该点的直线会在某个范围内,并且我们可以在这个范围内进行二分查找.

设二分查找的 $$mid$$ 为当前点最小的最强战斗力值(即当前点最小横纵截距之和),则

$$mid = \frac{kx_i – y_i}{k} + y_i – kx_i$$

将 $$k$$ 反解出来,得

$$k = (x_i + y_i – mid)$$ ± $$\frac{\sqrt{(x_i + y_i – mid)^2 – 4 x_i y_i}}{2 x_i}$$

注意到我们解出来的 $$k$$ 有两个,只要其中一个 $$k$$ 在该范围内即可. 剩下的就是普通的二分了.

我这代码常数真的很大……

发表评论