点到凸包切线

Kubic

2022-08-09 16:34:59

个人记录

给定一个点和一个凸包,要求在 O(\log n) 的时间内求出点到凸包的两个切线。

仔细想一想,你真的会吗。

如果点的横坐标比凸包上所有点都小或者大,那么可以把上下凸壳中分别二分。

否则可以按照这个点的横坐标把凸包分成左右两半,再在两半中分别二分即可。

是不是很简单。