Kubic
2022-08-09 16:34:59
给定一个点和一个凸包,要求在 O(\log n) 的时间内求出点到凸包的两个切线。
仔细想一想,你真的会吗。
如果点的横坐标比凸包上所有点都小或者大,那么可以把上下凸壳中分别二分。
否则可以按照这个点的横坐标把凸包分成左右两半,再在两半中分别二分即可。
是不是很简单。