题意：给一些建筑物，x表示横坐标,h表示高度，然后查询某些坐标x，问从该点看向天空的最大张角是多大。
解法：离线操作，读入所有数据，然后按x升序排序，对每一个查询的x，先从左到右，依次添加x坐标小于x的建筑物，加入一个建筑物的条件：
1.此建筑物高度大于栈中的前一个，这个必然是最优的。
2.加入这个建筑物后不能使相对斜率： stk[top-2]~stk[top-1] 比a[j]~stk[top-1]大(负数),即出现凹形，否则会出现这种：
如图，即中间那个根本没用了，加入第三根的时候就要判一下。
最后算这个查询x的左角度的时候，要先判断这个点跟栈中上面两个的关系，处理一下。
然后再从右到左扫一遍，最后就得出了左右角。
之前没考虑相对斜率，而是每次加建筑物的时候，只判断与此时的查询点的绝对斜率关系，这样的bug就是会形成上图中的情况。（好蒻）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define pi (acos(-1.0))
#define eps 1e-7
using namespace std;
#define N 100007 struct Query
{
double x;
double Lang,Rang;
int ind;
}ans[N]; struct node
{
double x,h;
}a[N];
int stk[N],top;
int cmp1(Query ka,Query kb) { return ka.x < kb.x; }
int cmp2(Query ka,Query kb) { return ka.ind < kb.ind; }
int cmpB(node ka,node kb) { return ka.x < kb.x; } int main()
{
int t,cs = ,i,j;
int n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].h);
sort(a+,a+n+,cmpB);
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%lf",&ans[i].x);
ans[i].ind = i;
}
sort(ans+,ans+m+,cmp1);
double now;
top = ;
j = ;
for(i=;i<=m;i++)
{
while(j <= n && a[j].x < ans[i].x)
{
while(top >= && a[j].h >= a[stk[top-]].h) //高度大于之前的，肯定更优
top--;
while(top >= && (a[j].h-a[stk[top-]].h)/(fabs(a[j].x-a[stk[top-]].x)) >= (a[stk[top-]].h-a[stk[top-]].h)/(fabs(a[stk[top-]].x-a[stk[top-]].x)))
top--; //相对斜率递减(负数)
stk[top++] = j;
j++;
}
while(top >= && a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x)) <= a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x)))
top--; //对这个点
now = a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x)); //最终答案为栈顶的建筑
ans[i].Lang = 180.0*atan2(now,1.0)/pi;
}
top = ; //反着来一遍
j = n;
for(i=m;i>=;i--)
{
while(j >= && a[j].x > ans[i].x)
{
while(top >= && a[j].h >= a[stk[top-]].h)
top--;
while(top >= && (a[j].h-a[stk[top-]].h)/(fabs(a[j].x-a[stk[top-]].x)) >= (a[stk[top-]].h-a[stk[top-]].h)/(fabs(a[stk[top-]].x-a[stk[top-]].x)))
top--;
stk[top++] = j;
j--;
}
while(top >= && a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x)) <= a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x)))
top--;
now = a[stk[top-]].h/(fabs(a[stk[top-]].x-ans[i].x));
ans[i].Rang = 180.0*atan2(now,1.0)/pi;
}
sort(ans+,ans+m+,cmp2);
printf("Case #%d:\n",cs++);
for(i=;i<=m;i++)
printf("%.10f\n",180.0-ans[i].Lang-ans[i].Rang);
}
return ;
}