about 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2961
分析:
直接做肯定是不行的吧,我们考虑分治,按时间分治,然后判断左边对右边的影响。
如何判断这个影响呢?我们首先知道,点在圆内或圆上,当且仅当:

很显然这是一个半平面,如果点在圆内或圆上,那么圆心就必须在这个半平面内。
我们对于分治左边插入的圆维护一个凸包,右边的半平面维护半平面的方向从小到大。
如果一个点在所有的圆内或圆上,那么凸包就在其对应的半平面内,暴力枚举显然是不可行的,那么我们考虑斜率为半平面斜率的直线与凸包的切点,如果这个切点在半平面内,那么凸包就在半平面内,否则就不是。这个我们很显然只需要按方向大小从小到大扫一遍即可。
时间复杂度
bzoj2961.cpp

← bzoj4066:简单题 三角剖分:sgu383:Caravans →
 
comments powered by Disqus