HDU 4946 Area of Mushroom(构造凸包)

时间:2022-03-20 20:52:29

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4946

题目大意:在一个平面上有n个点p1,p2,p3,p4....pn,每个点可以以v的速度在平面上移动,对于平面上任意一点,假设有唯一一个点pi从初始的位置到这个点的时间最短,那么就说平面上的这个点是属于pi这点管辖的。现在要你判断pi管辖的范围是不是无穷大的,如果是输出1,否则输出0;

  首先大致的方法就是构造凸包,不过要遵循一下前提:

  一定是只考虑速度最大的点,然后,如果两个点所在的位置与速度都是相同的,那么这两个点的结果肯定是0,但是在构造的凸包的时候必须要考虑这个点,因为直接去掉会对其它的点有影响,还有就是当所有的点的速度都是0的时候,就不用构造凸包了,因为所有的都直接输出0就好了,都不能移动嘛。