CodeforcesLuogu分析首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。接着用 $n-2$ 次询问一,求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。我们把两侧的点分开处理。对于某一侧的点(假设已按逆时针排列),显然它们到 $A_...
Luogu分析除了卡精度都很简单的题。显然二分答案,考虑如何 check。设抛物线为 $y=ax^2+bx$,那么对于每个 $i$ 都应有那么对于每个 $i$,$a,b$ 的解集都可以表示为两个半平面的交,因此我们只要把 $2\times mid$ 个半平面拿出来判断是否存在半平面交即可。这题卡精度卡的我想死了 QAQ代码// ================================...
LuoguLOJ分析将整个蛋糕看做平面图,由欧拉公式可得代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #inclu...
UVaLuoguVjudge分析感觉...挺傻逼的?锐角三角形和直角三角形似乎不是很好数的亚子,可以考虑拿总数 $n\choose 3$ 减掉钝角三角形的数量。枚举一个点 $A$ ,按极角序枚举另一个点 $B$ ,那么极角在 $(ang_B+\frac{\pi}{2},ang_B+\pi)$ 范围内的点 $C$ 都可以和 $A,B$ 组成一个钝角三角形。那么直接拿两个指针扫一下就好了。可以发...
UVaLuogu分析一道不错的数数题。首先可以知道,三角形总数是 $n\choose 3$ ,所以只需要求出所有三角形包含的点数之和即可。可以转化一下,变成求每个点被多少个三角形包含。这个东西等于 $n-1\choose 3$ 减去不包含这个点的三角形个数。于是我们重点考虑怎么求不包含一个点 $x$ 的三角形个数。把除了 $x$ 之外的所有点拿出来,按极角序排序后扫描。假设当前扫到了 $i$...
LuoguBZOJ文化课选手M_sea更博了!分析分治。按照“平面最近点对”那一套理论,选取一条中心线划成两半,这样子最小三角形会有三种情况:全部在中心线左边。全部在中心线右边。一部分在左边,一部分在右边。显然第一种和第二种递归下去即可,主要考虑第三种怎么处理。设当前的最小周长为 $ans$ ,那么先把所有离中心线的 $x$ 的差不超过 $ans$ 的点拿出来按 $y$ 排个序。枚举一个点 ...
Luogu分析发现这个凸包的周长等价于一堆直边加上一个半径为 $r$ 的圆。于是把每张信用卡的四个顶点拿出来,求一个凸包,再用这个凸包的周长加上 $2\pi r$ 就是答案了。具体怎么求出四个顶点,可以先求出中心点,然后再加上向四个方向的向量。这四个向量又可以通过旋转得到。然后就做完了。代码//It is made by M_sea #include <algorithm> #i...
LuoguBZOJ分析把每条边的长度和每个角的大小按顺序排列,可以组成一个环。把这个环在某条对称轴的地方断开,形成的串显然是回文的。于是把这个环倍长,然后长度 $> len$ 的回文串个数就是答案(这里的 $len$ 是环长)。直接跑 $\mathrm{manacher}$ 即可。具体的,长度可以不开根号,角的大小可以用叉积。然后最后的答案要 $/2$ ,因为每条对称轴被算了两次。具...
LuoguBZOJ双倍经验分析最小圆覆盖的板子题。首先将输入的点随机打乱,然后三重循环枚举三个点 $i$ 、 $j$ 、 $k$ 。如果 $i$ 不在当前圆内,将圆心设为 $i$ 。如果 $j$ 也不在圆内,将圆心设为 $i$ 和 $j$ 的中点。如果 $k$ 也不在圆内,将圆心设为 $△ijk$ 的外心。可以证明期望复杂度为 $O(n)$ 。代码//It is made by M_sea ...
Luogu分析将删除变成添加,然后用set来维护上凸壳即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cma...