题目大意：城市里有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;
}原文：http://blog.csdn.net/keshuai19940722/article/details/39475323