首页 > 代码库 > hdu 5033 Building(单调性+二分)

hdu 5033 Building(单调性+二分)

题目链接:hdu 5033 Building

题目大意:城市里有n座摩天大厦,给定每栋大厦的位置和高度,假定大厦的宽度为0。现在有q次查询,表示人站的位置,人的高度视为0,问说可以仰望天空的角度。

解题思路:比赛的时候用单调性优化直接给过了,对于每个大厦来说,记录左右两边与其形成斜率最大的大厦序号以及斜率,然后每次查询是,通过二分确认人所在位置属于哪两栋大厦之间,然后分别向左向右确认角度,在确认角度时,根据大厦记录的最大斜率进行判断。
以左边为例,

然后对于查询位置x:

这种解法仅仅是优化查询效率而已,对于极端数据(斜率一直处于递减),对于单次查询复杂度就变成了o(n),虽然测试样例没有这样的数据,但貌似不是正解。

C++ 优化查询
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 2 * 1e5 + 5; const double pi = atan(1.0) * 4; struct point { double x, h; bool operator < (const point& u) const { return x < u.x; } }p[maxn]; struct edge { int v; double k; void set (int v, double k) { this->v = v; this->k = k; } }l[maxn], r[maxn]; int N; inline double get_k(const point& a, const point& b) { return (a.h - b.h) / fabs(b.x - a.x); } void init () { scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%lf%lf\n", &p[i].x, &p[i].h); sort(p, p + N); l[0].set(-1, 0); for (int i = 1; i < N; i++) { int u = i - 1; while (l[u].v != -1 && l[u].k > get_k(p[u], p[i])) u = l[u].v; l[i].v = u; l[i].k = get_k(p[u], p[i]); } r[N-1].set(-1, 0); for (int i = N - 2; i >= 0; i--) { int u = i + 1; while (r[u].v != -1 && r[u].k > get_k(p[u], p[i])) u = r[u].v; r[i].v = u; r[i].k = get_k(p[u], p[i]); } } void solve () { int n; point q; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lf", &q.x); q.h = 0; int idx = lower_bound(p, p + N, q) - p; int mv = idx - 1; while (l[mv].v != -1 && l[mv].k > get_k(p[mv], q)) mv = l[mv].v; while (r[idx].v != -1 && r[idx].k > get_k(p[idx], q)) idx = r[idx].v; double R = pi - atan(get_k(p[mv], q)) + atan(get_k(q, p[idx])); printf("%.10lf\n", R / pi * 180); } } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { init(); printf("Case #%d:\n", kcas); solve(); } return 0; }

赛后和队友讨论了一下,觉得用离线算法应该是正解,将所有查询预先度入,然后统一按照x坐标排序,同样是以左边为例,维护斜率的单调栈,然后碰到询问点就直接在栈中二分,这样单次查询的复杂度就变成了o(logn)。


当处理到x2时,栈中存在<2>号边;当处理到x1询问时,栈中存在<3>,<4>,<5>号边,每次根据询问坐标对栈中的边进行二分。

C++ 二分
#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; const int maxn = 2 * 1e5 + 5; const double pi = atan(1.0) * 4; struct point { int idx; double x, h; point (int idx = 0, double x = 0, double h = 0) { this->idx = idx;; this->x = x; this->h = h; } bool operator < (const point& u) const { return x < u.x; } }; struct edge { int v; double k; edge (int v, double k) { this->v = v; this->k = k; } }; int N; double l[maxn], r[maxn]; vector<point> p; vector<edge> g; inline double get_k(const point& a, const point& b) { return (a.h - b.h) / fabs(b.x - a.x); } void init () { p.clear(); double x, h; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%lf%lf", &x, &h); p.push_back(point(0, x, h)); } scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%lf", &x); p.push_back(point(i, x, 0)); } sort(p.begin(), p.end()); } double bsearch (point u) { int L = 0, R = g.size(); while (L < R) { int mid = (L + R) / 2; if (g[mid].k > get_k(p[g[mid].v], u)) R = mid; else L = mid + 1; } L--; double k = p[g[L].v].h / fabs(p[g[L].v].x - u.x); return atan(k); } void solve () { g.clear(); g.push_back(edge(0, -1)); for (int i = 1; i < p.size(); i++) { if (p[i].idx > 0) { l[p[i].idx] = bsearch(p[i]); } else { int u = g.size() - 1; while (u && g[u].k > get_k(p[g[u].v], p[i])) { g.pop_back(); u--; } g.push_back(edge(i, get_k(p[g[u].v], p[i]))); } } g.clear(); g.push_back(edge(p.size()-1, -1)); int u = p.size() - 1; for (int i = p.size() - 2; i >= 0; i--) { if (p[i].idx > 0) { r[p[i].idx] = bsearch(p[i]); } else { int u = g.size() - 1; while (u && g[u].k > get_k(p[g[u].v], p[i])) { g.pop_back(); u--; } g.push_back(edge(i, get_k(p[g[u].v], p[i]))); } } for (int i = 1; i <= N; i++) printf("%.10lf\n", (pi - l[i] - r[i]) / pi * 180); } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { init(); printf("Case #%d:\n", kcas); solve(); } return 0; }

hdu 5033 Building(单调性+二分)