「清澄A1482」登顶计划 - 单调栈 + 计算几何

你在一座由$n$个点构成的山脉中爬山，第$i$个点坐标为$(x_i, y_i)$

你的爬山策略是：

• 一直往当前可见的最高点的方向走，也就是说你的策略是不断动态变化的

求从每个顶点出发，到达所能到达的最高点的路程分别是多少

加强版：

Links

清澄A1482

Solution

这是一道2013年的论文题，论文里讲得非常详细

首先考虑如何计算一个点向一侧能看到的最高峰

以左侧为例，设点$i$向左能看到的最高点为$L[i]$，则$i$左侧的所有点都在$i$与$L[i]$的连线之下

不难发现，$i$与$L[i]$即为$i$与向左的上凸壳的最后两个点。所以，可能看得更高的点一定是上凸壳上某一条线与它右侧的山峰的第一个交点或本身的顶点。

我们从前往后维护凸壳，每一次单调栈弹栈，就代表凸壳上的某一条线向右第一个相交。这样可以直接做单调栈来求出这些关键点。只有这些关键点才会对答案产生贡献。求出关键点后,也同样可以用单调栈求出每个关键点的$L[i]$和

设$H[i] = \max\{\max\{y_{L[i]}, y_{R[i]}\}, y_i\}$。我们发现对于某个点$i$，它确定向某个方向走后，至少会走到第一个$H[i] \le H[x]$的位置,而剩下的路线和直接从x号点出发相同。

于是可以从$x$到$i$连一条边,则整个图构成了一棵森林，我们将边权设为$x$到的距离，最后可以直接dfs一遍求出答案。

求向左向右第一个$H[x]$大于等于$H[i]$的$x$同样也可以用单调栈解决。

总时间复杂度

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef long double ld;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e6 + 100;
const ld eps = 1e-7;
const ld inf = 1e18;

struct point
{
	ld x, y;

	inline point operator + (const point &rhs) const { return (point){x + rhs.x, y + rhs.y}; }
	inline point operator - (const point &rhs) const { return (point){x - rhs.x, y - rhs.y}; }
};

namespace GEOM
{
	inline ld sqr (ld x) { return x * x; }

	inline int check (ld x) { if (x > eps) return 1; if (x < -eps) return -1; return 0; }
	
	inline ld cross (point a, point x, point y) { x = x - a, y = y - a; return x.x * y.y - x.y * y.x; }

	inline int check (point a, point x, point y) { return check(cross(a, x, y)); }

	inline point get_intersection (point a, point b, point c, point d)
	{
		ld k1 = (a.y - b.y) / (a.x - b.x), b1 = a.y - k1 * a.x;
		ld k2 = (c.y - d.y) / (c.x - d.x), b2 = c.y - k2 * c.x;
		ld x = (b2 - b1) / (k1 - k2);
		return (point){x, x * k1 + b1};
	}

	inline ld get_dis (point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
}

int NN, N, Stack[Maxn], top, Vis[Maxn];
point A[Maxn], B[2][Maxn], C[Maxn];

inline void Get_All_Point ()
{
	int cnt[2] = {0, 0};

	for (int k = 0; k < 2; ++k)
	{
		int d = k ? -1 : 1;
		Stack[top = 1] = 1;
		for (int i = 2; i <= N; ++i)
		{
			while (top > 1)
			{
				point now = A[Stack[top]], pre = A[Stack[top - 1]];
				int op = GEOM :: check (A[i], now, pre) * d;
				if (op > 0) break;
				if (op < 0 && Stack[top] != i - 1) B[k][++cnt[k]] = GEOM :: get_intersection (now, pre, A[i], A[i - 1]);
				--top;
			}
			if (top && A[Stack[top]].y < A[i].y) --top;
			Stack[++top] = i;
		}
		reverse (A + 1, A + N + 1);
	}

	reverse (B[1] + 1, B[1] + cnt[1] + 1);

	int pos1 = 1, pos2 = 1, pos3 = 1, len = 0;
	while (1)
	{
		if (pos1 > N && pos2 > cnt[0] && pos3 > cnt[1]) break;
		ld a = A[pos1].x, b = B[0][pos2].x, c = B[1][pos3].x;
		if (pos1 > N) a = inf;
		if (pos2 > cnt[0]) b = inf;
		if (pos3 > cnt[1]) c = inf;

		if (GEOM :: check(a - b) <= 0 && GEOM :: check(a - c) <= 0) C[++len] = A[pos1], Vis[len] = 1, ++pos1;
		else if (GEOM :: check(b - a) <= 0 && GEOM :: check(b - c) <= 0) C[++len] = B[0][pos2], ++pos2;
		else C[++len] = B[1][pos3], ++pos3;
	}

	for (int i = 1; i <= len; ++i) A[i] = C[i];
	N = len;
}

int L[Maxn], R[Maxn];
ld H[Maxn], Sum[Maxn];

inline void Get_LR ()
{
	Stack[top = 1] = 1;
	for (int i = 2; i <= N; ++i)
	{
		while (top && GEOM :: check (A[Stack[top]].y - A[i].y) < 0) --top;
		while (top > 1 && GEOM :: check (A[i], A[Stack[top]], A[Stack[top - 1]]) <= 0) --top;
		if (top) L[i] = Stack[top];
		Stack[++top] = i;
	}

	Stack[top = 1] = N;
	for (int i = N - 1; i >= 1; --i)
	{
		while (top && GEOM :: check (A[Stack[top]].y - A[i].y) < 0) --top;
		while (top > 1 && GEOM :: check (A[i], A[Stack[top]], A[Stack[top - 1]]) >= 0) --top;
		if (top) R[i] = Stack[top];
		Stack[++top] = i;
	}

	for (int i = 1; i <= N; ++i) H[i] = max(max(A[L[i]].y, A[R[i]].y), A[i].y);
	for (int i = 2; i <= N; ++i) Sum[i] = Sum[i - 1] + GEOM :: get_dis (A[i], A[i - 1]);
}

int Begin[Maxn], To[Maxn << 1], Next[Maxn << 1], e;
ld W[Maxn << 1];

inline void add_edge (int x, int y, ld z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

inline void Build_Graph ()
{
	Stack[top = 1] = 1;
	for (int i = 2; i <= N; ++i)
	{
		while (top && GEOM :: check (H[Stack[top]] - H[i]) < 0) --top;
		if ((L[i] || R[i]) && GEOM :: check (A[L[i]].y - A[R[i]].y) > 0) add_edge (Stack[top], i, Sum[i] - Sum[Stack[top]]);
		Stack[++top] = i;
	}

	Stack[top = 1] = N;
	for (int i = N - 1; i >= 1; --i)
	{
		while (top && GEOM :: check (H[Stack[top]] - H[i]) < 0) --top;
		if ((L[i] || R[i]) && GEOM :: check (A[L[i]].y - A[R[i]].y) < 0) add_edge (Stack[top], i, Sum[Stack[top]] - Sum[i]);
		Stack[++top] = i;
	}
}

ld Ans[Maxn];

inline void dfs (int x)
{
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		Ans[y] = Ans[x] + W[i];
		dfs(y);
	}
}

inline void Solve ()
{
	Get_All_Point ();
	Get_LR ();
	Build_Graph ();

	for (int i = 1; i <= N; ++i) if(L[i] + R[i] == 0) dfs(i);
	for (int i = 1; i <= N; ++i) if (Vis[i]) printf("%.8Lf\n", Ans[i]);
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) A[i].x = read<int>(), A[i].y = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("doe.in", "r", stdin);
	freopen("doe.out", "w", stdout);
#endif

	Input();
	Solve();

	return 0;
}