HDU 5033 Building (單調棧)

http://acm.hdu.edu.cn/showproblem.php?pid=5033

Building
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 303    Accepted Submission(s): 85
Special Judge      

Problem Description Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position x i with its height h i. All skyscrapers located in different place. The skyscrapers had no width, to make it simple. As the skyscrapers were so high, Matt could hardly see the sky.Given the position Matt was at, he wanted to know how large the angle range was where he could see the sky. Assume that Matt's height is 0. It's guaranteed that for each query, there is at least one building on both Matt's left and right, and no building locate at his position.  

Input The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

Each test case begins with a number N(1<=N<=10^5), the number of buildings.

In the following N lines, each line contains two numbers, x i(1<=x i<=10^7) and h i(1<=h i<=10^7).

After that, there's a number Q(1<=Q<=10^5) for the number of queries.

In the following Q lines, each line contains one number q i, which is the position Matt was at.  

Output For each test case, first output one line "Case #x:", where x is the case number (starting from 1).

Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).  

Sample Input

3
3
1 2
2 1
5 1
1
4
3
1 3
2 2
5 1
1
4
3
1 4
2 3
5 1
1
4
        

Sample Output

Case #1:
101.3099324740
Case #2:
90.0000000000
Case #3:
78.6900675260
        

Source 2014 ACM/ICPC Asia Regional Beijing Online  

題意：

給出N幢摩天大樓的位置和高度，有Q次查詢，問在某點處能看見天空的角度範圍。

分析：

一開始的想法是維護一個單調棧，首先離線資料并排序，然後左右掃兩邊。單調棧内大樓的高度要遞減，然後判斷棧頂元素是否比它的前一個更優，如果不是則出棧。但是如果棧頂元素比它前一個優，并不能保證是全局最優的。

正确的維護方法是保證單調棧内的大樓高度遞減，而且要使得這些大樓的最高點構成一個類似凸包的形狀，或者說是凸包的一部分，然後再判斷棧頂元素和它前一個比是否更優，如果不是則出棧。這樣最後的棧頂元素就是待查詢點在某方向的視角最大範圍，記錄下這個方向向量即可，最後角度隻要求兩向量間的夾角即可。

(ugly code,maybe I could attend ioccc)

/*
 *
 *  Author  :  fcbruce
 *
 *  Date  :  2014-09-21 13:07:59 
 *
 */
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld "%I64d"
#else
  #define lld "%lld"
#endif

#define maxm 100010
#define maxn 100010

using namespace std;

struct node
{
  double x,h;
  bool operator < (const node &n)const
  {
    return x<n.x;
  }
}sky[maxn];

struct __q
{
  double x;
  int h;
  bool operator < (const __q &q)const
  {
    return x<q.x;
  }
}q[maxm];

inline double
dot(const pair<double,double> &v1,const pair<double,double> &v2)
{
  return v1.first*v2.first+v1.second*v2.second;
}

inline double
len(const pair<double,double> &v)
{
  return sqrt(sqr(v.first)+sqr(v.second));
}

pair<double,double> v_l[maxn],v_r[maxn];

int st[maxn];

int
main()
{
#ifdef FCBRUCE
  freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE
  
  int T_T,__=0;
  scanf("%d",&T_T);
  
  while (T_T--)
  {
    int n,m;
    
    scanf("%d",&n);
    for (int i=0;i<n;i++)
      scanf("%lf%lf",&sky[i].x,&sky[i].h);
      
    sort(sky,sky+n);
    
    scanf("%d",&m);
    
    for (int i=0;i<m;i++)
    {
      scanf("%lf",&q[i].x);
      q[i].h=i;
    }
    
    sort(q,q+m);
    
    for (int i=0,j=0,top=-1;i<m;i++)
    {
      while (j<n && sky[j].x<q[i].x)
      {
        while (top>-1 && sky[j].h>sky[st[top]].h-eps) top--;

        while (top>0 && (sky[st[top]].h-sky[j].h)*(sky[st[top]].x-sky[st[top-1]].x)<
                        (sky[st[top-1]].h-sky[st[top]].h)*(sky[j].x-sky[st[top]].x)+eps) top--;
        
        st[++top]=j++;
        
        while (top>0 && sky[st[top]].h*(q[i].x-sky[st[top-1]].x)<
                        sky[st[top-1]].h*(q[i].x-sky[st[top]].x)+eps) top--;
      }
      
      while (top>0 && sky[st[top]].h*(q[i].x-sky[st[top-1]].x)<
                      sky[st[top-1]].h*(q[i].x-sky[st[top]].x)+eps) top--;

      v_l[q[i].h]=make_pair(sky[st[top]].x-q[i].x,sky[st[top]].h);
    }
    
    for (int i=m-1,j=n-1,top=-1;i>=0;i--)
    {
      while (j>=0 && sky[j].x>q[i].x)
      {
        while (top>-1 && sky[j].h>sky[st[top]].h-eps) top--;
        
        while (top>0 && (sky[st[top]].h-sky[j].h)*(sky[st[top-1]].x-sky[st[top]].x)<
                        (sky[st[top-1]].h-sky[st[top]].h)*(sky[st[top]].x-sky[j].x)+eps) top--;
                        
        st[++top]=j--;
        
        while (top>0 && sky[st[top]].h*(sky[st[top-1]].x-q[i].x)<
                        sky[st[top-1]].h*(sky[st[top]].x-q[i].x)+eps) top--;
      }
      
      while (top>0 && sky[st[top]].h*(sky[st[top-1]].x-q[i].x)<
                      sky[st[top-1]].h*(sky[st[top]].x-q[i].x)+eps) top--;
      
      v_r[q[i].h]=make_pair(sky[st[top]].x-q[i].x,sky[st[top]].h);
    }
    
    printf("Case #%d:\n",++__);
    
    for (int i=0;i<m;i++)
      printf("%.10f\n",acos(dot(v_l[i],v_r[i])/(len(v_r[i])*len(v_l[i])))*180/PI);
  }
  
  return 0;
}