Building（单调栈+凸包）

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

Recommend

hujie | We have carefully selected several similar problems for you: 6521 6520 6519 6518 6517

思路：

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

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

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

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

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<cmath>

const int maxn=1e5+5;
typedef long long ll;
using namespace std;
const double pi = acos(-1.0);
pair<double, double> p[maxn];
pair<double, int> pos[maxn];
double ans[maxn];
int stack[maxn], n, Q;

double slope(const int a, const int b)
{
    return -(p[a].second - p[b].second) / (p[a].first - p[b].first);
}

double angle(const int a, const int b)
{
    return atan((pos[b].first - p[a].first) / p[a].second);
}

void solve()
{
    int j = 0, top = 0;
    for(int i = 0; i < Q; ++i)
    {
        while(j < n && p[j].first < pos[i].first)
        {
            while(top > 0 && p[stack[top]].second <= p[j].second)   top--;
            while(top >= 2 && slope(stack[top], j) < slope(stack[top - 1], stack[top])) top--;
            stack[++top] = j;
            j++;
        }
        while(top >= 2 && angle(stack[top], i) > angle(stack[top - 1], i))    top--;
        ans[pos[i].second] += angle(stack[top], i);
    }
}

int main()
{
    int T, kase;
    scanf("%d", &T);
    for(int kase = 1; kase <= T; ++kase)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%lf%lf", &p[i].first, &p[i].second);
        sort(p, p + n);
        
        scanf("%d", &Q);
        for(int i = 0; i < Q; ++i)
        {
            scanf("%lf", &pos[i].first);
            pos[i].second = i;
            ans[i] = 0.0;
        }
        sort(pos, pos + Q);
        solve();
        reverse(p, p + n);
        reverse(pos, pos + Q);
        for(int i = 0; i < n; ++i)  p[i].first = -p[i].first;
        for(int i = 0; i < Q; ++i)  pos[i].first = -pos[i].first;
        solve();
        printf("Case #%d:
", kase);
        for(int i = 0; i < Q; ++i)
            printf("%.10lf
", ans[i]/pi*180.0);
    }
    return 0;
}