题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4752
题意:给出一个抛物线和一个简单多边形。求抛物线在多边形内部的长度。
思路:首先求出多边形所有边和抛物线的交点。这里要注意:
(1)边和抛物线相切不算,因为整个抛物线在边的另一侧;
(2)如下,上面两种相交都是不能算的,下面一种要算。
算出所有交点之后,那么每相邻两个交点与抛物线的关系必然是抛物线交替进入-离开。下面对于一段[x1,x2]计算抛物线的长度。
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); } }