这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 | |||
2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2 [2020/07/31 14:02] 2sozx [E] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2 [2020/07/31 14:05] (当前版本) 2sozx [E] |
||
---|---|---|---|
行 10: | 行 10: | ||
* 题意:给定 $n$ 条平行与 $x$ 轴的线段并且 $y_i>0$ ,现在选择一个向量,将这些线段沿着向量平移到 $x$ 轴,期间线段不能有相交,顶点相交除外,问最后平移到 $x$ 轴后左右端点距离最小值是多少。$(n\le2000,-10^6\le xl_i<xr_i\le10^6,1\le y_i\le10^6)$ | * 题意:给定 $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$ 的一次函数,因此可以构造出两个凸壳,然后对于每个可行的向量在上面二分查找即可。注意答案会很大,极大值要开够。 | + | * 题解:有个很显然的结论,如果要达到最小值必然会有两条线段顶点相交,因此我们可以枚举两条线段相交,记录相交时的向量,显然对于两条的线段,如果此时向量位于顶点相交的向量内部,则这两条线段最后会相交,因此我们可以通过扫描线来判断什么向量是可行的。\\ \\ 对于一个向量我们要快速判断通过这个向量移动后 $x$ 坐标的最大值和最小值是多少,考虑一个点 $x_i,y_i$ 通过向量移动会到什么位置。令向量为 $v=(a,b),b<0$ ,这个点最后会到 $(x_i-y_i*a/b,0)$ ,横坐标为关于 $x_i,y_i$ 的一次函数,将一个线段看作两个点,因此可以构造出两个凸壳,然后对于每个可行的向量在上面二分查找即可。注意答案会很大,极大值要开够。 |