HDU - 5033 Building

HDU - 5033 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
題意：給你n棟樓，每棟樓有高度和坐標，現在詢問你人站在某個位置，能看到的天空的角度
思路：將詢問的人和樓組合在一起，排序後，維護一個凸的高度下降的單調棧(可以動手畫一下)，然後每次查詢到人的位置的時候，維護單調棧，使得圖形是凸的，那麼棧首和這個人就能構成答案了，還有是樓的時候也要維護這個棧，那麼前後各遍歷一次，就能通過正切值求解了
#include 
#include 
#include 
#include 
#include 
#include 
typedef __int64 ll;
using namespace std;

const double PI = acos(-1.0);
const int maxn = 100005;

struct Node {
	int x, h;
	bool operator <(const Node &a)const {
		return x < a.x;
	}
} node[maxn<<2], stk[maxn<<2];
double ans[maxn];
int n, q;

int check(Node &a, Node &b, Node c) {
	if (c.h <= 0)
		c.h = 0;
	return (ll)(a.h - c.h) * (c.x - b.x) >= (ll)(b.h - c.h) * (c.x - a.x);
}

double getAngle(Node a, Node b) {
	return atan((double)(b.x-a.x)/(double)(a.h));
}

void cal() {
	int head = 0;
	for (int i = 0; i < n+q; i++) {
		if (node[i].h <= 0) {
			while (head >= 2 && check(stk[head-2], stk[head-1], node[i]))
				head--;
			ans[-node[i].h] += getAngle(stk[head-1], node[i]);
		}
		else {
			while (head && stk[head-1].h <= node[i].h)
				head--;
			while (head >= 2 && check(stk[head-2], stk[head-1], node[i]))
				head--;
			stk[head++] = node[i];
		}
	}
}

int main() {
	int t, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d%d", &node[i].x, &node[i].h);
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d", &node[i+n].x);
			node[i+n].h = -i;
		}

		memset(ans, 0, sizeof(ans));
		sort(node, node+n+q);

		cal();

		reverse(node, node+n+q);
		for (int i = 0; i < n+q; i++)
			node[i].x = 10000000 - node[i].x;

		cal();

		printf("Case #%d:\n", cas++);
		for (int i = 0; i < q; i++)
			printf("%.10lf\n", ans[i] * 180.0 / PI);
	}
	return 0;
}