CVBB ACM Team

分类：计算几何

题意：给定 $n$ 条平行与 $x$ 轴的线段并且 $y_i>0$ ，现在选择一个向量，将这些线段沿着向量平移到 $x$ 轴，期间线段不能有相交，顶点相交除外，问最后平移到 $x$ 轴后左右端点距离最小值是多少。$(n\le2000,-10^6\le xl_i<xr_i\le10^6,1\le y_i\le10^6)$

题解：有个很显然的结论，如果要达到最小值必然会有两条线段顶点相交，因此我们可以枚举两条线段相交，记录相交时的向量，显然对于两条的线段，如果此时向量位于顶点相交的向量内部，则这两条线段最后会相交，因此我们可以通过扫描线来判断什么向量是可行的。

对于一个向量我们要快速判断通过这个向量移动后 $x$ 坐标的最大值和最小值是多少，考虑一个点 $x_i,y_i$ 通过向量移动会到什么位置。令向量为 $v=(a,b),b<0$ ，这个点最后会到 $(x_i-y_i*a/b,0)$ ，横坐标为关于 $x_i,y_i$ 的一次函数，将一个线段看作两个点，因此可以构造出两个凸壳，然后对于每个可行的向量在上面二分查找即可。注意答案会很大，极大值要开够。

comment：考虑的细节挺多，最后这个二分要思考一下，比赛时没想到

分类：计算几何、$dp$

题意：给定$n$个点($n \leq 2000$)，选出尽量少的点，使得从起点开始沿着给定顺序两点连线移动一个半径为$d(d\leq 10^6)$的圆能够覆盖住所有的点。

题解：$n^2$预处理后$n^2$转移$dp$

利用切线角度的合并可以很轻松的找到对于每个起点，选择哪些点可以覆盖其中间所有的点，$dp$过程中就可以在满足情况的点对之间进行转移，但是有可能会出现回溯的点序(详细图片在这里)，因此我们需要正反各扫一次。

同时有一个小技巧就是利用旋转和分类处理可以防止$atan2$的奇妙结果影响答案

comment：正反遍历实在太顶了，同时旋转处理角度的技巧有get到

分类：

题意：

题解：

comment：