http://acm.hdu.edu.cn/showproblem.php?pid=5033
题意：给一个数轴， 是地面。
地面上有n座楼，给出m个人，分别站在m个位置上，问每个位置能看见多大角度的天空（二维平面）
数据范围：
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.可以根据求凸包的过程求解，把人当成高度为0的楼插入数据中。
第一遍，按下标从左到右扫描，对于当前这个楼，如果与top楼形成的角度的绝对值，比楼top-1与楼top形成的角度绝对值还小（可用叉积判），就把top楼弹出，也就是，单调栈里维护的是角度绝对值增大的建筑群，这样能保证每个人看到的视野都是正确的。
同理，把下标反过来扫一遍，得到是右边的视野角度。
最后加起来就是答案
复杂度O（n）
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <map> #include <set> #include <vector> using namespace std; const double PI=acos(-1.0); struct node { double h; double x; int id; node() {} node (double a,double b) { x=a,h=b; } node operator - (const node &t)const { return node(x-t.x,h-t.h); } int operator * (const node &t)const /// 叉积 : 有向面积 { return x*t.h-h*t.x; } }; node tm[100123*2]; int top; double ans[100123*2]; node aa[100123*2]; bool cmp(node a,node b) { return a.x<b.x; } bool judge(const node& a,const node& b,const node &c) { return ((b-a)*(c-b))>=0; } double angle(const node &a, const node &b) { return atan((double)a.h / (double)(b.x - a.x)); } int main() { int n,i; int t; cin>>t; int cnt=1; while(t--) { memset(ans,0,sizeof (ans)); cin>>n; for (int i=1; i<=n; i++) { scanf("%lf%lf",&aa[i].x,&aa[i].h); } int cun=n; int q; cin>>q; for (int i=1; i<= q; i++) { scanf("%lf",&aa[++cun].x); aa[cun].h=0; aa[cun].id=i; } sort(aa+1,aa+1+cun,cmp); int top=0; for (int i=1; i<=cun; i++) { while(top>=2 && judge (tm[top-1],tm[top],aa[i])) top--; if (aa[i].h>0) tm[++top]=aa[i]; else ans[aa[i].id]+=angle(tm[top],aa[i]); } reverse(aa+1, aa+1+cun); top=0; for (int i=1;i<=cun;i++) aa[i].x=1e7-aa[i].x; for (int i=1; i<=cun; i++) { while(top>=2 && judge (tm[top-1],tm[top],aa[i])) top--; if (aa[i].h>0) tm[++top]=aa[i]; else ans[aa[i].id]+=angle(tm[top],aa[i]); } printf("Case #%d:\n",cnt++); for (int i=1;i<=q;i++) printf("%.10lf\n", (PI - ans[i]) / PI * 180.0);//ans[i]存的是看不到的角度 } return 0; }
