AT2702 Fountain Walk

前言

校内模拟考试的其中一题,细节很多,测的时候 WA 了几个点,后来才改对

题面

题目链接 (luogu.org/problem/AT2702)

有一个 $10^8 \times 10^8$ 的网格图,相邻格点间上下左右的距离都是 $100m$ ,格点上面有 $n$ 个圆,每个圆半径为 $10m$ ,同一行或同一列最多只有一个圆

现在要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ ,只能沿着网格的边或圆周走,输出最短距离(保留 13 位小数)。

思路

对于圆 $i$,只有 $x_i\in\lbrack min(x_1,x_2),max(x_1,x_2)\rbrack,y_i\in\lbrack min(y_1,y_2),max(y_1,y_2)\rbrack$ 时,才是有用的。

从起点到终点,在不走回头路(例如从左下走到右上,每一步必须向右或者向上)的情况下,走过越多的圆越优($\frac{20\mathrm\pi}4<20$)。

因为不能走回头路,所以选择的圆中 $y$ 坐标是单调的。因为每行每列没有重复的圆,不难看出,即为求解满足范围内圆坐标的 $LIS$。

为了方便,如果 $y_1$ > $y_2$ ,那么交换起点和终点(使求的坐标单调上升)。

如果起点在终点左边,从左到右枚举每个点,如果该点是有用的,那么将它的坐标加入待求 $LIS$ 的数组中。如果起点在终点右边,那么倒着枚举即可。

然后对该数组求一遍 $LIS$,对于每个圆,可以使总路程减少 $20-5\mathrm\pi$ 米。

注意:如果在序列中点的个数等于起终点的间距(线的条数)(如下图),那么必然有一个点是会被经过半个圆的,总答案需要加上 $5\mathrm\pi$ 。

代码

暂无评论

发送评论


				
上一篇
下一篇