HDU 4752 Polygon（抛物线长度积分）

struct point{ double x,y; void get() { cin>>x>>y; } point(){} point(double _x,double _y) { x=_x; y=_y; } point operator+(point a) { return point(x+a.x,y+a.y); } point operator-(point a) { return point(x-a.x,y-a.y); } point operator*(double t) { return point(x*t,y*t); }};point p[N];int n;double L,R,a,b,c;int sgn(double x){ if(x>1e-8) return 1; if(x<-1e-8) return -1; return 0;}vector<double> V;double func(double x){ return a*x*x+b*x+c;}void deal(point p,point q){ if(sgn(p.x-q.x)==0) { double y=func(p.x); if(p.y>q.y) swap(p,q); if(sgn(y-p.y)>0&&sgn(y-q.y)<0) V.pb(p.x); return; } double k=(q.y-p.y)/(q.x-p.x); double A=a; double B=b-k; double C=c+k*p.x-p.y; double temp=B*B-4*A*C; if(sgn(temp)<=0) return; temp=sqrt(temp); double x1=(-B-temp)/(2*A); double x2=(-B+temp)/(2*A); if(p.x>q.x) swap(p,q); if(sgn(x1-p.x)>0&&sgn(x1-q.x)<0) V.pb(x1); if(sgn(x2-p.x)>0&&sgn(x2-q.x)<0) V.pb(x2);}void deal(point p1,point p,point p2){ if(sgn(func(p.x)-p.y)) return; p1=p+(p1-p)*1e-3; p2=p+(p2-p)*1e-3; if(sgn(func(p1.x)-p1.y)*sgn(func(p2.x)-p2.y)==-1) V.pb(p.x);}double cal(double x){ double A=4*a*a; double B=4*a*b; double C=b*b+1; double temp=A*x*x+B*x+C; return (2*A*x+B)/(4*A)*sqrt(temp)+(4*A*C-B*B)/(8*A*sqrt(A))*log(fabs(2*A*x+B+2*sqrt(A)*sqrt(temp)));}double cal(double l,double r){ if(l<L) l=L; if(r>R) r=R; if(l>=r) return 0; return cal(r)-cal(l);}int main(){ Rush(n) { scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&L,&R); int i; FOR0(i,n) p[i].get(); p[n]=p[0]; p[n+1]=p[1]; V.clear(); FOR0(i,n) deal(p[i],p[i+1]); FOR1(i,n) deal(p[i-1],p[i],p[i+1]); sort(V.begin(),V.end()); double ans=0; for(i=0;i+1<SZ(V);i+=2) ans+=cal(V[i],V[i+1]); PR(ans); }}