hdoj 5033 凸包

hdoj 5033

題意：若幹高樓， 一個人站中間，問他看到藍天的最大角度，或者說是左邊看到的和右邊看到的大樓的仰角和的補角。

思路：

三條黑線代表高樓，分别表示1号、2号、3号高樓，紅點和黃點是人所在的地點。

當人在紅點時，顯然左邊所有樓中3号樓仰角最大，但是到黃點的時候，2号樓仰角最大，這時就可以删掉3号樓，因為黃點右邊的點也不會被3号樓擋住；考慮如果1号樓之前有更高的樓層，黃點的仰角可以更大的話，那麼1、2、3号樓都會被删掉。

是以這個問題就轉化成了一個求凸包的問題，兩邊分别求凸包就可以得到詢問點左右最大的仰角。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

struct Point {
    double x, h;
    int id;
    void input() {
        scanf("%lf %lf", &x, &h);
    }
    Point(){}
    Point(int a, int b): x(a), h(b){}
    bool operator < (const Point &i) const {
        return x < i.x;
    }
};
Point point[200020], stk[200020];
double ans[100020];
long long gradjudge(Point a, Point b, Point c) {
    long long t1 = (a.x - b.x) * (c.h - b.h);
    long long t2 = (a.h - b.h) * (c.x - b.x);
    return t1 - t2;
}
const double PI = acos(-1.0);
main() {
    int t, n, nq;
    scanf("%d", &t);
    for(int cas = 1; cas <= t; cas++) {
        memset(ans, 0, sizeof ans);
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) point[i].input();
        scanf("%d", &nq);
        for(int i = 1; i <= nq; i++) scanf("%lf", &point[i + n].x), point[i + n].h = 0, point[i + n].id = i;
        n = n + nq;
        sort(point + 1, point + n + 1);
        int k = 0;
        for(int i = 1; i <= n; i++)  {
            while(k > 1 && gradjudge(stk[k - 2], stk[k - 1], point[i]) <= 0) k--;
            if(point[i].h == 0) {
                ans[point[i].id] += atan((point[i].x - stk[k - 1].x) / stk[k - 1].h);
            //    printf("%f %f %f\n", stk[k - 1].h, point[i].x - stk[k - 1].x, ans[point[i].id]);
            }
            stk[k++] = point[i];
        }
        k = 0;
        for(int i = n; i >= 1; i--) {
            while(k > 1 && gradjudge(stk[k - 2], stk[k - 1], point[i]) >= 0) k--;
            if(point[i].h == 0) {
                ans[point[i].id] += atan((-point[i].x + stk[k - 1].x) / (stk[k - 1].h));
             //   printf("%f %f %f\n", stk[k - 1].h, -point[i].x + stk[k - 1].x, ans[point[i].id]);
            }
            stk[k++] = point[i];
        }
        printf("Case #%d:\n", cas);
        for(int i = 1; i <= nq; i++){
            printf("%.10f\n", ans[i] / PI * 180.0);
        }
    }
}