#include #include #include #include #include #include #include using namespace std; const double eps=1e-10; const int INF=1<<29; const double PI=acos(-1.0); int doublecmp(double x){ if(fabs(x)0) return tempa-tempb; else return tempa-tempb+2*PI; } Vector Rotate(Vector a,double rad){ return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad)); } Vector Normal(Vector a){ double L=Length(a); return Vector(-a.y/L,a.x/L); } Point GetLineProjection(Point p,Point a,Point b){ Vector v=b-a; return a+v*(Dot(v,p-a)/Dot(v,v)); } Point GetLineIntersection(Point p,Vector v,Point q,Vector w){ Vector u=p-q; double t=Cross(w,u)/Cross(v,w); return p+v*t; } int ConvexHull(Point* p,int n,Point* ch){ sort(p,p+n); int m=0; for(int i=0;i1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--){ while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } if(n>0) m--; return m; } double Heron(double a,double b,double c){ double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c)); } bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){ double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1); double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1); return doublecmp(c1)*doublecmp(c2)<0&&doublecmp(c3)*doublecmp(c4)<0; } double CutConvex(const int n,Point* poly, const Point a,const Point b, vector result[3]){ vector points; Point p; Point p1=a,p2=b; int cur,pre; result[0].clear(); result[1].clear(); result[2].clear(); if(n==0) return 0; double tempcross; tempcross=Cross(p2-p1,poly[0]-p1); if(doublecmp(tempcross)==0) pre=cur=2; else if(tempcross>0) pre=cur=0; else pre=cur=1; for(int i=0;i0) cur=0; else cur=1; if(cur==pre){ result[cur].push_back(poly[(i+1)%n]); } else{ p1=poly[i]; p2=poly[(i+1)%n]; p=GetLineIntersection(p1,p2-p1,a,b-a); points.push_back(p); result[pre].push_back(p); result[cur].push_back(p); result[cur].push_back(poly[(i+1)%n]); pre=cur; } } sort(points.begin(),points.end()); if(points.size()<2){ return 0; } else{ return Length(points.front()-points.back()); } } double DistanceToSegment(Point p,Segment s){ if(s.a==s.b) return Length(p-s.a); Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b; if(doublecmp(Dot(v1,v2))<0) return Length(v2); else if(doublecmp(Dot(v1,v3))>0) return Length(v3); else return fabs(Cross(v1,v2))/Length(v1); } bool isPointOnSegment(Point p,Segment s){ return doublecmp(DistanceToSegment(p,s))==0; } int isPointInPolygon(Point p, Point* poly,int n){ int wn=0; for(int i=0;i0&&d1<=0&&d2>0)wn++; if(k<0&&d2<=0&&d1>0)wn--; } if(wn) return 1; else return 0; } double PolygonArea(vector p){ double area=0; int n=p.size(); for(int i=1;i* Polygons){ int count=n-1; bool vis[9999];memset(vis,0,sizeof vis); Point star=arr[0].a,pre=arr[0].a,cur=arr[0].b,purpose=arr[0].b;vis[0]=true; int mark; while(purpose!=star){ double theta=-INF; for(int i=0;i0){ for(int i=0;i= 0) continue; if (doublecmp(ip[0].p.y - O.y) > 0) ip[0].p = GetLineIntersection(l.p,l.v, O, Point(1.0, 0)); for (int i = 0; i < 2; i++) ip[i].pos = i & 1, allpoint[idx++] = ip[i]; } } sort(allpoint, allpoint + idx); int cnt = 0; double sum = 0, lp = x - v1 * time, rp = x, ls = lp; for (int i = 0; i < idx; i++) { if (allpoint[i].p.x > rp) break; if (allpoint[i].p.x < lp) { if (allpoint[i].pos) cnt--; else cnt++; } else { if (allpoint[i].pos) { if (cnt == 1) sum += allpoint[i].p.x - ls; cnt--; } else { if (cnt == 0) ls = allpoint[i].p.x; cnt++; } } } if (cnt > 0) sum += rp - ls; printf("Case %d: %.4f\n", cas++, sum / v1); } }