2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
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$ 的一次函数，将一个线段看作两个点，因此可以构造出两个凸壳，然后对于每个可行的向量在上面二分查找即可。注意答案会很大，极大值要开够。 |
2020-2021/teams/farmer_john/2sozx/codeforces_round_660_div._2.1596175379.txt.gz · 最后更改: 2020/07/31 14:02 由 2sozx
