Problem Description
South China Algorithm University (SCAU) 是一个生态环境优秀的校园。走在校道上，你可以看见牛羊猫狗鸡鸭鹅，等等。
牛在校道上走当然不是没人管的。放牛大叔通常会带N头大牛小牛去到一片宽阔的草地上吃草，草地上有M块大石头，放牛大叔会在石头上坐着，看着这群大牛小牛。当然，并非所有石头的位置都是那么好，放牛大叔要看着所有的牛，所以挑选的位置P的视野必须小于180度（也就是在他面前，最左边的牛A和最右边的牛B与P形成的角度∠APB不能大于等于180度）。
现在给出N头大牛小牛的位置，然后给出M个石头的位置，请你分别求出每个石头是否可以看着全部牛。如果可以，求出相应位置的视野度数。（可以假设大牛小牛不会在石头上吃草，而且大牛小牛都很聪明，不会在吃同一位置的草）
Input
有多组数据输入。
每组数据第一个数是牛的个数N，之后N行每行有两个数(Xi, Yi)，表示牛的位置。
紧接着的是石头的个数M，之后M行有每行有两个数(Xj, Yj)，表示石头的位置。
数据范围：
3≤M,N≤1000
|Xi|,|Yi|≤1000000
输入数据保证不会全部牛都在同一条直线上。
Output
对于每一块石头输出一行。如果这个位置的视野可以看到全部的牛，那么输出这个位置的视野的度数是多少（保留两位小数）。否则，输出“Bad Position”。
Sample Input
4 0 0 1 0 1 1 0 1 3 0.5 0.5 1 0.5 2 0
Sample Output
Bad Position Bad Position 45.00
1 #include<iostream> 2 #include<algorithm> 3 #include<math.h> 4 #include<stdio.h> 5 using namespace std; 6 #define PI 3.1415926535898 7 struct point 8 { 9 double x,y; 10 }; 11 point p[1005],res[1005]; 12 int n,top; 13 double Dist(const point &arg1, const point &arg2) 14 { 15 return sqrt( 1.0*(arg1.x - arg2.x)*(arg1.x - arg2.x) + (arg1.y - arg2.y)*(arg1.y - arg2.y) ); 16 } 17 bool multi(point p0,point p1,point p2) 18 { 19 return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y); 20 } 21 bool cmp(const point &a,const point &b) 22 { 23 point temp=p[0]; 24 double xmt=(a.x-temp.x)*(b.y-temp.y)-(b.x-temp.x)*(a.y-temp.y); 25 if(xmt) //向量不共线就按逆时针旋转 26 return xmt>0; 27 return Dist(a,temp)>Dist(b,temp);//向量共线取最长的。 28 } 29 void graham()//p[0]是左下角的元素 30 { 31 res[0]=p[0]; 32 sort(p+1,p+n,cmp);//按照极角排序 33 res[1]=p[1]; 34 res[2]=p[2]; 35 top=2; 36 for(int i=3; i<n; i++) 37 { 38 while(multi(p[i],res[top],res[top-1])) 39 top--; 40 res[++top]=p[i]; 41 } 42 } 43 bool check(point temp) 44 { 45 int i,m=multi(temp,res[0],res[1]); 46 for(i=1;i<top;i++) 47 { 48 if(multi(temp,res[i],res[i+1])!=m)return 0; 49 } 50 if(multi(temp,res[i],res[0])!=m)return 0; 51 return 1; 52 } 53 void work(point temp) 54 { 55 int bi,en; 56 bi=en=0; 57 for(int i=1;i<=top;i++) 58 { 59 if(multi(temp,res[i],res[bi]))bi=i; 60 if(multi(temp,res[en],res[i]))en=i; 61 } 62 double ans=atan2(res[en].y-temp.y,res[en].x-temp.x)-atan2(res[bi].y-temp.y,res[bi].x-temp.x); 63 if(ans<0.0)ans+=2*PI; 64 ans=ans*180/PI; 65 printf("%.2lf\n",ans); 66 } 67 int main() 68 { 69 int i,mina,m; 70 point temp; 71 while(~scanf("%d",&n)) 72 { 73 scanf("%lf%lf",&p[0].x,&p[0].y); 74 mina=0; 75 for(i=1; i<n; i++) 76 { 77 scanf("%lf%lf",&p[i].x,&p[i].y); 78 if(p[i].y<p[mina].y||(p[i].y==p[mina].y&&p[i].x<p[mina].x)) 79 mina=i; 80 } 81 swap(p[0].x,p[mina].x),swap(p[0].y,p[mina].y); 82 graham(); 83 scanf("%d",&m); 84 while(m--) 85 { 86 scanf("%lf%lf",&temp.x,&temp.y); 87 if(check(temp)) 88 { 89 printf("Bad Position\n"); 90 } 91 else 92 { 93 work(temp); 94 } 95 } 96 } 97 }