Luogu分析除了卡精度都很简单的题。显然二分答案,考虑如何 check。设抛物线为 $y=ax^2+bx$,那么对于每个 $i$ 都应有那么对于每个 $i$,$a,b$ 的解集都可以表示为两个半平面的交,因此我们只要把 $2\times mid$ 个半平面拿出来判断是否存在半平面交即可。这题卡精度卡的我想死了 QAQ代码// ================================...
Luogu分析首先求出每个亲戚管辖的区域,这个可以通过半平面交求出。具体的,将该亲戚与其它所有亲戚的中垂线拿出来跑半平面交即可。然后考虑建这样一个图:对于每个亲戚,往与它的管辖区域相邻的亲戚连边。这样子只要 BFS 求出走到外面的最短路就是答案了。注意要判掉 $n=0$ 的沙雕情况,不然你可能会 WA / TLE / RE ...代码// ==========================...
LuoguLOJ分析假设有两个三角形 $\triangle ABO$ 和 $\triangle CDO$ ,且 $S_{\triangle ABO}<S_{\triangle CDO}$ 。设 $A(x_a,y_a),B(x_b,y_b),C(x_c,y_c),D(x_d,y_d),O(x,y)$ 。首先写出可以发现是直线的形式,于是暴力求出所有这些之间然后跑半平面交就可以得到合法的 ...
LuoguBZOJ分析首先,斜率相同的两条直线,纵截距大的在上面。所以先按斜率从小到大排序,对于斜率相同的只保留纵截距最大的。然后,维护一个单调栈,斜率单调递增。考虑一条新的直线满足什么条件才能覆盖掉栈顶。经过一番分析后发现,如果新的直线与$s[top-1]$的交点在$s[top]$的右边,那么$s[top]$会被覆盖掉。这里的$s$是栈。注意,一开始要把斜率最小的直线放进来。然后这题就做完...