1 /*  2 ID:esxgx1  3 LANG:C++  4 PROG:B  5 */  6 #include <cstdio>  7 #include <cstring>  8 #include <iostream>  9 #include <algorithm> 10 #include <cmath> 11 using namespace std; 12  13 const int maxn = 100007; 14  15  16 const double PI = acos(-1.0); 17  18 typedef pair<double, double> po; 19 #define px        first 20 #define py        second 21  22 const double EPS = 1e-9; 23 inline int sgn(double x){return x < -EPS ? -1 : x > EPS;} 24 template<typename T> T det(const T &x0, const T &y0, const T &x1, const T &y1) {return x0*y1 - x1*y0;} 25 double det(const po &p0, const po &p1) {return det(p0.px, p0.py, p1.px, p1.py);} 26 po operator -(const po &a, const po &b) { return make_pair(a.px - b.px, a.py - b.py);} 27 template<typename T> int clkws(const T &p, const T &p1, const T &p2){ return sgn(det(p1 - p, p2 - p));} 28  29 struct obss { 30     po p; 31     int id; 32 } obs[maxn]; 33  34 po bl[maxn]; 35 double ll[maxn], rr[maxn]; 36  37 po st[maxn]; 38 int sttf; 39  40 int cmp(const po &a, const po &b) 41 { 42   return a.px < b.px; 43 } 44  45 int cmp2(const obss &a, const obss &b) 46 { 47   return a.p.px < b.p.px; 48 } 49  50 int main(void) 51 { 52     #ifndef ONLINE_JUDGE 53     freopen("in.txt", "r", stdin); 54     #endif 55  56     int tt; 57     scanf("%d", &tt); 58     for(int t=1; t<=tt; ++t) { 59         int nn; 60         scanf("%d", &nn); 61         for(int i=0; i<nn; ++i) 62             scanf("%lf%lf", &bl[i].px, &bl[i].py); 63         sort(bl, bl+nn, cmp); 64  65         int qq; 66         scanf("%d", &qq); 67         for(int i=0; i<qq; ++i) { 68             scanf("%lf", &obs[i].p.px); 69             obs[i].id = i; 70         } 71         sort(obs, obs+qq, cmp2); 72  73         int att; 74  75         sttf = 0, att = 0; 76         for(int i=0; i<qq; ++i) { 77             for(; bl[att].px < obs[i].p.px; ++att) { 78                 //while(sttf>0 && st[sttf].py <= bl[att].py) --sttf; 79                 while(sttf>1 && clkws(st[sttf-1], st[sttf], bl[att]) >= 0) --sttf; 80                 st[++sttf] = bl[att]; 81  82             } 83             while(sttf>1 && clkws(st[sttf-1], st[sttf], obs[i].p) >= 0) --sttf; 84             ll[obs[i].id] = PI - atan2(st[sttf].py - obs[i].p.py, st[sttf].px - obs[i].p.px); 85             //printf("ll[%d] : %f st(%f %f) obs(%f %f)\n", i, ll[i], st[sttf].px, st[sttf].py, obs[i].px, obs[i].py); 86         } 87  88         sttf = 0, att = nn-1; 89  90         for(int i=qq; i--; ) { 91             for(; bl[att].px > obs[i].p.px; --att) { 92                 //while(sttf>0 && st[sttf].py <= bl[att].py) --sttf; 93                 while(sttf>1 && clkws(st[sttf-1], st[sttf], bl[att]) <= 0) --sttf; 94                 st[++sttf]= bl[att]; 95                 //printf("bl[%d] : %f %f st[%d](%f %f) obs(%f %f)\n", att, bl[att].px, bl[att].py, rr[i], sttf, st[sttf].px, st[sttf].py, obs[i].px, obs[i].py); 96             } 97             while(sttf>1 && clkws(st[sttf-1], st[sttf], obs[i].p) <= 0) --sttf; 98             rr[obs[i].id] = atan2(st[sttf].py - obs[i].p.py, st[sttf].px - obs[i].p.px); 99             //printf("rr[%d] : %f st[%d](%f %f) obs(%f %f)\n", i, rr[i], sttf, st[sttf].px, st[sttf].py, obs[i].px, obs[i].py);100         }101         printf("Case #%d:\n", t);102         for(int i=0; i<qq; ++i)103             printf("%.9f\n", (PI - ll[i] - rr[i])/PI * 180);104     }105     return 0;106 }