首页 > 代码库 > HDU 5033 (单调栈维护凸包) Building

HDU 5033 (单调栈维护凸包) Building

题意:

一个人在x轴上,他的左右两侧都有高楼,给出楼的横坐标Xi和高度Hi还有人的位置pos,求人所能看到的天空的最大角度。

分析:

将建筑物和人的位置从左到右排序,对于每个位置利用栈求一次人左边建筑物的凸包,找到一个最小的角度,然后对称一下,再找一个右边的建筑物的最小角度,两个角度加起来就是答案。

将人左边的建筑物从左到右扫描,下面两种情况会出栈:

  1. 栈顶元素楼高小于等于当前扫描到的楼高,因此这是一个单调的栈
  2. 栈顶两个楼顶所在直线的斜率 小于 栈顶的楼顶和当前楼顶所在直线的斜率(这里的斜率指的是绝对值),这保证了栈中所有楼顶的构成的曲线是个凸包

然后再求人的视线和竖直线的最小角度时,如果栈顶的楼的人的视线与水平线夹角 大于 栈中第二个楼所成的夹角,则出栈

 

代码中用到了STL里的pair,pair相当于有两个元素first 和 second的结构体,所定义的小于是判断容器x是否小于y。该操作先判断x.first < y.first的关系,然后再判断x.second < y.second的关系。所以特别需要注意的是:T1和T2必须支持“<”操作符,否则编译报错。

 

虽然没有图,可是如果理解了的话,心中自有图。=_=||

 1 //#define LOCAL 2 #include <cstdio> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6  7 const double pi = acos(-1.0); 8 const int maxn = 100000 + 10; 9 10 pair<double, double> p[maxn];11 pair<double, int> pos[maxn];12 double ans[maxn];13 int stack[maxn], n, Q;14 15 double slope(const int a, const int b)16 {17     return -(p[a].second - p[b].second) / (p[a].first - p[b].first);18 }19 20 double angle(const int a, const int b)21 {22     return atan((pos[b].first - p[a].first) / p[a].second);23 }24 25 void solve()26 {27     int j = 0, top = 0;28     for(int i = 0; i < Q; ++i)29     {30         while(j < n && p[j].first < pos[i].first)31         {32             while(top > 0 && p[stack[top]].second <= p[j].second)   top--;33             while(top >= 2 && slope(stack[top], j) < slope(stack[top - 1], stack[top])) top--;34             stack[++top] = j;35             j++;36         }37         while(top >= 2 && angle(stack[top], i) > angle(stack[top - 1], i))    top--;38         ans[pos[i].second] += angle(stack[top], i);39     }40 }41 42 int main()43 {44     #ifdef LOCAL45         freopen("5033in.txt", "r", stdin);46     #endif47 48     int T, kase;49     scanf("%d", &T);50     for(int kase = 1; kase <= T; ++kase)51     {52         scanf("%d", &n);53         for(int i = 0; i < n; ++i)54             scanf("%lf%lf", &p[i].first, &p[i].second);55         sort(p, p + n);56         57         scanf("%d", &Q);58         for(int i = 0; i < Q; ++i)59         {60             scanf("%lf", &pos[i].first);61             pos[i].second = i;62             ans[i] = 0.0;63         }64         sort(pos, pos + Q);65         solve();66 67         reverse(p, p + n);68         reverse(pos, pos + Q);69         for(int i = 0; i < n; ++i)  p[i].first = -p[i].first;70         for(int i = 0; i < Q; ++i)  pos[i].first = -pos[i].first;71         solve();72 73         printf("Case #%d:\n", kase);74         for(int i = 0; i < Q; ++i)75             printf("%.10lf\n", ans[i]/pi*180.0);76     }77 78     return 0;79 }
代码君

 

HDU 5033 (单调栈维护凸包) Building