1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 #include <map> 5 #include <cstring> 6 #include <set> 7 #include <bitset> 8 #include <cstdio> 9 #include <cmath>10 11 #define esp 1e-812 #pragma comment(linker, "/STACK:102400000,102400000")13 #define in freopen("solve_in.txt", "r", stdin);14 #define pf(x) ((x)*(x))15 #define bug(x) printf("Line %d: >>>>>>\n", (x));16 #define lson l, m, rt<<117 #define rson m+1, r, rt<<1|118 #define pb push_back19 #define mp make_pair20 #define pi acos(-1.0)21 22 typedef unsigned short US;23 24 25 using namespace std;26 27 const int maxn = (int)1e5 + 100;28 int sta[maxn*2];29 int dblcmp(double x) {30     if(fabs(x) < esp) return 0;31     return x > 0 ? 1 : -1;32 }33 struct Node {34     double x, y;35     int type, id;36     bool operator < (const Node &o)const {37         return dblcmp(x-o.x) < 0;38     }39 } p[maxn*2];40 41 double cal(int x, int y) {42     return (p[y].y-p[x].y)/(p[y].x-p[x].x);43 }44 int l[maxn], r[maxn];45 double ans[maxn];46 double x[maxn];47 48 int main() {49 50     int T;51     int n, q;52     for(int t = scanf("%d", &T); t <= T; t++) {53         printf("Case #%d:\n", t);54         int top = 0;55         scanf("%d", &n);56         int cnt = 0;57         for(int i = 1; i <= n; i++) {58             scanf("%lf%lf", &p[cnt].x, &p[cnt].y);59             p[cnt++].type = 0;60         }61         scanf("%d", &q);62         for(int i = 1; i <= q; i++) {63             scanf("%lf", &p[cnt].x);64             p[cnt].y = 0.0;65             p[cnt].id = i;66             x[i] = p[cnt].x;67             p[cnt++].type = 1;68         }69         sort(p, p+cnt);70         top = 0;71         for(int i = cnt-1; i >= 0; i--) {72             while(top >= 2 && cal(i, sta[top]) < cal(sta[top], sta[top-1]))73                 top--;74            if(p[i].type){75                 int id = p[i].id;76                 r[id] = sta[top];77            }78             sta[++top] = i;79         }80         top = 0;81         for(int i = 0; i < cnt; i++){82             while(top >= 2 && cal(i, sta[top]) > cal(sta[top], sta[top-1]))83                 top--;84             if(p[i].type){85                 int id = p[i].id;86                 l[id] = sta[top];87             }88             sta[++top] = i;89         }90         for(int i = 1; i <= q; i++){91             double d1 = sqrt(pf(p[l[i]].y) + pf(p[l[i]].x-x[i]));92             double d2 = sqrt(pf(p[r[i]].y) + pf(p[r[i]].x-x[i]));93             double tmp = acos(fabs(p[l[i]].x-x[i])/d1) + acos(fabs(p[r[i]].x-x[i])/d2);94             tmp = (pi-tmp)/pi*180.0;95             printf("%.10f\n", tmp);96         }97     }98     return 0;99 }