Ps: 在思考ingress自动规划连边的时候顺便想到的一个题.
题:
Ingress里要连多重来刷ap. 这是一种简化的情况.
假设平面上有点(A), (B), (C_1, \dots , C_n).
其中(C_1 , \dots , C_n)在直线(AB)同侧.
要连一个多重就要选一些点( { C_{a_i} } ), 使得( \Delta ABC_{a_1}, \Delta ABC_{a_2}, \dots \Delta ABC_{a_m} ) 依次包含. 即( C_{a_i} )在( \Delta ABC_{a_{i-1}} ) 内.
然后每个(C_i)都有个权值( W_i ), 求所有方案中最大的权值和.
另:
把权值和最大改成权值积最大, 对( 998244353 )取模. 让一群人写高精去然后再随便把高精卡T掉哈哈哈哈哈哈哈.
解法: (口糊的请打脸)
大概是个dp题.
把(C_i)按照离直线(AB)的距离排序即可保证拓补序. (其实这题我觉得有意思的地方就是这个了. 然而太简单)
然后就是找平面上某个三角形里的最大(f)值. KD树搞之. (AFO太久的我已经不知道KD树是什么了. 似乎有人告诉过我KD树这么用保证不到时间复杂度.)
印象中KD树常年被用来打脸和被打脸.
也许有更方便的搞法? 然而我的数据结构实在太渣ovo.
就酱.