hdu 4736 This Is The Job The Bear Finds(2013年成都ACM网络赛)
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#define eps 1e-10#define sqr(a) ((a)*(a))#define pi (2.0*asin(1.0))using namespace std;double ma[100010];int sig(double a){return (a>eps)-(a<-eps);}typedef struct point{double x,y;point(double xx=0,double yy=0):x(xx),y(yy){}}vector;struct node{double ang,d;point c;}th[10010];point pt[10010];bool operator < (point a,point b){return a.x<b.x || (a.x==b.x && a.y<b.y);}vector operator - (point a,point b){return vector(a.x-b.x,a.y-b.y);}point operator + (point a,vector b){return point(a.x+b.x,a.y+b.y);}vector operator * (vector a,double b){return vector(a.x*b,a.y*b);}vector operator / (vector a,double b){return vector(a.x/b,a.y/b);}double dot(vector a,vector b){return a.x*b.x+a.y*b.y;}double cross(vector a,vector b){return a.x*b.y-a.y*b.x;}double len(vector a){return sqrt(sqr(a.x)+sqr(a.y));}double angle(vector a,vector b){double d=dot(a,b)/len(a)/len(b);if(sig(d-1)==0) return 0;if(sig(d+1)==0) return pi;return acos(d);}double dis(point a,point b,point p){return fabs(cross(b-a,p-a))/len(b-a);}vector rot(vector a,double b){double s=sin(b),c=cos(b);return vector(a.x*c-a.y*s,a.x*s+a.y*c);}vector rsize(vector a,double b){b/=len(a);return vector(a.x*b,a.y*b);}point bcenter(int n,double &l){point p,s;double tp,area=0,tpx=0,tpy=0;point t1=pt[0],t2=pt[0];p=pt[0];l=0;for(int i=1;i<=n;i++){s.x=pt[i==n ? 0 : i].x;s.y=pt[i==n ? 0 : i].y;if(s<t1) t1=s;else if(t2<s) t2=s;l+=len(pt[i-1]-s);tp=cross(p,s);area+=tp/2;tpx+=(p.x+s.x)*tp;tpy+=(p.y+s.y)*tp;p.x=s.x;p.y=s.y;}if(sig(area)==0) s=(t1+t2)/2;else {s.x=tpx/(6*area);s.y=tpy/(6*area);}return s;}point getp(point p,vector v,point cp,double r){double a=v.x,b=p.x-cp.x,c=v.y,d=p.y-cp.y;double e=sqr(a)+sqr(c),f=2*(a*b+c*d),g=sqr(b)+sqr(d)-sqr(r);double del=sqr(f)-4*e*g;double t=(-f+sqrt(del))/(2*e);return p+v*t;}int main(){int i,j,k,u,t,n,m,cnt,my,cas=1;double l,sl,rad,lp,lq,ang1,ang2,ds,ll;point ct,ct1,ct2,g;vector v,w;scanf("%d",&t);while(t--){scanf("%d",&n);my=0;for(i=0;i<n;i++){scanf("%lf%lf",&pt[i].x,&pt[i].y);if(sig(pt[my].x-pt[i].x)>0) my=i;}scanf("%lf%lf%d",&ct.x,&ct.y,&m);while(sig(cross(pt[my]-ct,pt[(my-1+n)%n]-pt[my]))>0) my=(my-1+n)%n;g=bcenter(n,sl); v=ct-g;ll=len(v);ct1=ct;th[0].c=ct;for(j=my,k=0;k<n;k++){u=(j+k)%n;lp=len(pt[u]-ct1);ct2=getp(pt[u],pt[(u+1)%n]-pt[u],g,ll);th[k+1].ang=th[k].ang+angle(ct1-g,ct2-g); th[k+1].d=th[k].d+len(pt[u]-ct2)-lp; th[k+1].c=ct2;ct1=ct2;}for(i=0;i<m;i++){scanf("%lf",&l);cnt=(int)l/sl;l=l-cnt*sl;rad=cnt*2*pi;int right=n,left=1,mid=(n+1)/2;double tmp1,tmp2;while(left<=right){tmp1=l-th[mid].d;tmp2=l-th[mid-1].d; if(sig(tmp1)==0) {mid++;break;}if(sig(tmp2)==0) break;if(sig(tmp1)<0 && sig(tmp2)>0) break;if(sig(tmp1)>0) left=mid+1;else right=mid-1;mid=(left+right)/2;}j=mid; if(left>right) j++;rad+=th[j-1].ang;l-=th[j-1].d; if(sig(l)>0){u=(my+j-1)%n;lp=len(pt[u]-g);lq=len(th[j-1].c-pt[u])+l;ang1=acos((sqr(lp)+sqr(ll)-sqr(lq))/(2*lp*ll));ang2=ang1-angle(pt[u]-g,th[j-1].c-g);rad+=ang2; }ma[i]=rad/pi*180;}printf("Case #%d:\n",cas++);for(i=0;i<m;i++) printf("%.3lf\n",ma[i]);}return 0;}