hdu5033 最大仰望角

题意：
      给你n个楼房排成一条直线，楼房可以看成是宽度为1的线段，然后给你m组询问，每组询问给你一个坐标，输出在当前坐标仰望天空的可视角度。

思路：

      n比较大，O(n*m)肯定跪，其实我们可以优化掉凹形的时候，比如当前询问点为x,对于右侧，往右跑的时候，我们只跑升序的就行了，这样我们只要开一个数组记录当前点最近的右侧的上升点就行了，到达当前点的时候，如果不满足，可以直接跳到记录的那个点上去，比赛的时候没敢敲，感觉时间根本过不去，后来听说可以，我又重新敲了一下，结果AC了，感觉应该是随机数据的原因，也就是根本达不到O(n*m).还有，找小标的时候可以用二分去找，刚才写的时候脑袋一热突然就用容器去弄的，就是开了一个set和一个map，一个找值一个哈希值（不建议这样写，二分就行了，还省时间）。具体看代码。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<set>
#include<map>


using namespace std;

typedef struct
{
double X ,Y;
}Point;

typedef struct
{
double x ,h;
}NODE;

NODE node[110000];
int merl[110000];
int merr[110000];

bool camp(NODE a ,NODE b)
{
return a.x < b.x;
}

int main ()
{
int t ,i ,j ,n ,m ,cas = 1;
double x;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
set<double>my_st;
map<double ,int>mark;
my_st.clear();
mark.clear();
for(i = 1 ;i <= n ;i ++)
{
scanf("%lf %lf" ,&node[i].x ,&node[i].h);
merl[i] = merr[i] = i;
}
sort(node + 1 ,node + n + 1 ,camp);
for(i = 1 ;i <= n ;i ++)
{
my_st.insert(node[i].x);
mark[node[i].x] = i;
}

for(i = 1 ;i <= n ;i ++)
{
for(j = i - 1 ;j >= 1 ;j --)
{
if(node[j].h > node[i].h)
{
merl[i] = j;
break;
}
if(j == merl[j]) break;
}
}

for(i = n ;i >= 1 ;i --)
{
for(j = i + 1 ;j <= n ;j ++)
{
if(node[j].h > node[i].h)
{
merr[i] = j;
break;
}
if(j == merr[j]) break;
}
}
scanf("%d" ,&m);
printf("Case #%d:\n" ,cas ++);
while(m--)
{
scanf("%lf" ,&x);
int r = mark[*my_st.lower_bound(x)];
int l = r - 1;

double max = node[r].h * 1.0 / (node[r].x - x);
int idr = r;
while(merr[r] != r)
{
r = merr[r];
if(max < node[r].h * 1.0 / (node[r].x - x))
{
max = node[r].h * 1.0 / (node[r].x - x);
idr = r;
}
}
max = node[l].h * 1.0 / (x - node[l].x);
int idl = l;
while(merl[l] != l)
{
l = merl[l];
if(max < node[l].h * 1.0 / (x - node[l].x))
{
max = node[l].h * 1.0 / (x - node[l].x);
idl = l;
}
}
Point A ,B ,C;
A.X = node[idl].x ,A.Y = node[idl].h;
B.X = x ,B.Y = 0;
C.X = node[idr].x ,C.Y = node[idr].h;
double x1 = A.X - x ,y1 = A.Y;
double x2 = C.X - x ,y2 = C.Y;
double Ang = ((x1 * x2) + (y1 * y2)) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2));

Ang = acos(Ang);
printf("%.10lf\n" ,Ang * 180.0 / acos(-1.0));
}
}
return 0;
}