题意：
一个人在x轴上，他的左右两侧都有高楼，给出楼的横坐标Xi和高度Hi还有人的位置pos，求人所能看到的天空的最大角度。
分析：
将建筑物和人的位置从左到右排序，对于每个位置利用栈求一次人左边建筑物的凸包，找到一个最小的角度，然后对称一下，再找一个右边的建筑物的最小角度，两个角度加起来就是答案。
将人左边的建筑物从左到右扫描，下面两种情况会出栈：
- 栈顶元素楼高小于等于当前扫描到的楼高，因此这是一个单调的栈
- 栈顶两个楼顶所在直线的斜率 小于 栈顶的楼顶和当前楼顶所在直线的斜率(这里的斜率指的是绝对值)，这保证了栈中所有楼顶的构成的曲线是个凸包
然后再求人的视线和竖直线的最小角度时，如果栈顶的楼的人的视线与水平线夹角 大于 栈中第二个楼所成的夹角，则出栈
代码中用到了STL里的pair，pair相当于有两个元素first 和 second的结构体，所定义的小于是判断容器x是否小于y。该操作先判断x.first < y.first的关系，然后再判断x.second < y.second的关系。所以特别需要注意的是：T1和T2必须支持“<”操作符，否则编译报错。
虽然没有图，可是如果理解了的话，心中自有图。=_=||
//#define LOCAL
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; const double pi = acos(-1.0);
const int maxn = + ; pair<double, double> p[maxn];
pair<double, int> pos[maxn];
double ans[maxn];
int stack[maxn], n, Q; double slope(const int a, const int b)
{
return -(p[a].second - p[b].second) / (p[a].first - p[b].first);
} double angle(const int a, const int b)
{
return atan((pos[b].first - p[a].first) / p[a].second);
} void solve()
{
int j = , top = ;
for(int i = ; i < Q; ++i)
{
while(j < n && p[j].first < pos[i].first)
{
while(top > && p[stack[top]].second <= p[j].second) top--;
while(top >= && slope(stack[top], j) < slope(stack[top - ], stack[top])) top--;
stack[++top] = j;
j++;
}
while(top >= && angle(stack[top], i) > angle(stack[top - ], i)) top--;
ans[pos[i].second] += angle(stack[top], i);
}
} int main()
{
#ifdef LOCAL
freopen("5033in.txt", "r", stdin);
#endif int T, kase;
scanf("%d", &T);
for(int kase = ; kase <= T; ++kase)
{
scanf("%d", &n);
for(int i = ; i < n; ++i)
scanf("%lf%lf", &p[i].first, &p[i].second);
sort(p, p + n); scanf("%d", &Q);
for(int i = ; i < Q; ++i)
{
scanf("%lf", &pos[i].first);
pos[i].second = i;
ans[i] = 0.0;
}
sort(pos, pos + Q);
solve(); reverse(p, p + n);
reverse(pos, pos + Q);
for(int i = ; i < n; ++i) p[i].first = -p[i].first;
for(int i = ; i < Q; ++i) pos[i].first = -pos[i].first;
solve(); printf("Case #%d:\n", kase);
for(int i = ; i < Q; ++i)
printf("%.10lf\n", ans[i]/pi*180.0);
} return ;
}
代码君