谁说最小乘积生成树是取log了ovo题意都不一样好么.
首先这个东西一定在一个像是下凸壳一样的东西上.其实是一个反比例函数的k的最小值.
把x和y的和看作坐标,求在(x0,y0)与(x1,y1)中间的一个点,为了平均分配,要取那个三角形最大,于是可以用叉积弄出一个式子来当作x和y的系数,这样就可以直接kruskal求最小生成树了.
如果求出来的点在这个线段上,那这个区间就不用再找了.否则还得去两边继续递归.
然后最初的左端点和右端点就取x的最小生成树和y的最小生成树就好了.
这个时间复杂度似乎还是没有保证啊.有点像自适应simpson的感觉,虽然这个肯定是精确的.然后跑起来也比较快.有意思.
这个玩意还是比较好写的.虽然中间kruskal把0打成1,看了半天ovo