盗张图：来自http://blog.csdn.net/xuechelingxiao/article/details/39494433
题目大意：有一排建筑物坐落在一条直线上，每个建筑物都有一定的高度，给出一个X坐标，高度为0，问X位置能看到的视角是多少度。如图：
图一：
图二：
图一为样例一，图二为样例三，红色部分为高楼，蓝色虚线为视角的最大范围。
思路：维护一个上凸的凸壳，递减的。也就是这样的。
分别找一下左边的和右边的就可以求出来答案
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = ;
const double PI = acos(-);
struct Node {
int x, h;
bool operator < (const Node &a) const {
return x < a.x;
}
}node[maxn<<], stack[maxn<<];
int T, n, q;
double ans[maxn]; int check(Node &a, Node &b, Node c) {
if (c.h <= )
c.h = ;
return (long long)(b.x - a.x) * (c.h - a.h) >= (long long)(c.x - a.x) * (b.h - a.h);//前面一定要加上long long ，或者用double也行，不然他的乘积有可能爆int
}
double getAngle(const Node &p1, const Node &p2)
{
return atan((double)(p2.x - p1.x) / (double)p1.h);
}
void solve()
{
int head = ;
for (int i = ; i < n + q; i++)
{
if (node[i].h <= )
{
while (head >= && check(stack[head - ], stack[head - ], node[i]))
head--;
ans[-node[i].h] += getAngle(stack[head - ], node[i]);
}
else
{
while (head && stack[head - ].h <= node[i].h)
head--;
while (head >= && check(stack[head - ], stack[head - ], node[i]))
head--;
stack[head++] = node[i];
}
}
}
int main()
{
int kase = ;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d %d", &node[i].x, &node[i].h);
scanf("%d", &q);
for (int i = ; i < q; i++)
{
scanf("%d", &node[i + n].x);
node[i + n].h = -i;
}
memset(ans, , sizeof(ans));
sort(node, node + n + q);
solve();
reverse(node, node + n + q);
for (int i = ; i < n + q; i++)
node[i].x = - node[i].x;
solve();
printf("Case #%d:\n", ++kase);
for (int i = ; i < q; i++)
printf("%.10f\n", ans[i] * 180.0 / PI);
}
return ;
}