本文共 3033 字，大约阅读时间需要 10 分钟。
题意是说在水平轴上有很多建筑物（没有宽度），知道每个建筑物的位置与高度。有m个查询，每次查询位置x所能看到的天空的角度。
方法是将建筑与查询一起排序，从左往右计算一遍，如果是建筑物，则比较最后两个（当前的与队尾的）斜率与队尾两个的斜率比较，如果较小则入队，否则一直出队尾元素直至满足条件（因为斜率为负数，斜率较小说明越堵）。
如果是查询，同样的比较这个位置与队尾的斜率同队尾两个元素的斜率比较，直至满足小于的关系结束，这时计算垂直方向左侧的夹角
最后从右往左计算右边，求和便是答案
1 #pragma comment(linker, "/STACK:1677721600") 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 using namespace std; 16 #define INF 0x3f3f3f3f 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, (L + R)>>1 19 #define rson k<<1|1, ((L + R)>>1) + 1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FIN freopen("in.txt", "r", stdin) 24 #define FOUT freopen("out.txt", "w", stdout) 25 #define rep(i, a, b) for(int i = a; i <= b; i ++) 26 #define dec(i, a, b) for(int i = a; i >= b; i --) 27 28 template T MAX(T a, T b) { return a > b ? a : b; } 29 template T MIN(T a, T b) { return a < b ? a : b; } 30 template T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 31 template T LCM(T a, T b) { return a / GCD(a,b) * b; } 32 33 //typedef __int64 LL; 34 typedef long long LL; 35 const int MAXN = 200000 + 100; 36 const int MAXM = 110000; 37 const double eps = 1e-8; 38 LL MOD = 1000000007; 39 const double PI = 4.0 * atan(1.0); 40 41 int T, N, Q; 42 int x, h; 43 struct Node { 44 int x, h; 45 Node(int _x = 0, int _h = -1) { 46 x = _x; h = _h; 47 } 48 }node[MAXN]; 49 int sta[MAXN >> 1]; 50 double ans_l[MAXN >> 1], ans_r[MAXN >> 1]; 51 52 int cmp_up(Node A, Node B) { return A.x < B.x; } 53 54 int cmp_down(Node A, Node B) { return A.x > B.x; } 55 56 double pre(int r, int l) { 57 return (double)(node[r].h - node[l].h) / fabs(1.0 * node[r].x - node[l].x); 58 } 59 60 double pre(Node a, int l) { 61 return (double)(a.h - node[l].h) / fabs(1.0 * a.x - node[l].x); 62 } 63 64 void record_ans(double *angle) { 65 int tp = 0; 66 rep (i, 1, N + Q) { 67 if(node[i].h < 0) { 68 while(tp >= 2 && pre(Node(node[i].x, 0), sta[tp - 1]) - pre(sta[tp - 1], sta[tp - 2]) > eps) tp --; 69 angle[-node[i].h] = atan(fabs(1.0 * node[i].x - node[sta[tp - 1]].x) / node[sta[tp - 1]].h); 70 } 71 else { 72 while(tp >= 2 && pre(i, sta[tp - 1]) - pre(sta[tp - 1], sta[tp - 2]) > eps) tp --; 73 sta[tp++] = i; 74 } 75 } 76 } 77 78 int main() 79 { 80 // FIN; 81 cin >> T; 82 rep (cas, 1, T) { 83 scanf("%d", &N); 84 rep (i, 1, N) { 85 scanf("%d %d", &x, &h); 86 node[i] = Node(x, h); 87 } 88 scanf("%d", &Q); 89 rep (i, 1, Q) { 90 scanf("%d", &x); 91 node[N + i] = Node(x, -i); 92 } 93 sort(node + 1, node + 1 + N + Q, cmp_up); 94 record_ans(ans_l); 95 sort(node + 1, node + 1 + N + Q, cmp_down); 96 record_ans(ans_r); 97 cout << "Case #" << cas <<":" << endl; 98 rep (i, 1, Q) { 99 printf("%.10f\n", (ans_l[i] + ans_r[i]) * 180 / PI);100 }101 }102 return 0;103 }
转载于:https://www.cnblogs.com/gj-Acit/p/4662644.html