|
|
back to boardeps:: 1e-5 is AC, 1e-9 WA... RT Re: eps:: 1e-5 is AC, 1e-9 WA... what's the principle of the solution? i've tried to construct laser-lines one after another with the smallest distance, and then to find dots of intersections line[i] and line[i+1], then find intersection of line[i+1] and line[i+2] and after that find the distance between dot[1] and dot[2], dot[2] and dot[3] and so on. But that's a big problem: line[i] can intersect line[i+1] in dot[1], that can later occur outside of the figure, formed with intersects of line[i+1000] and line[i+1001]. What's the solution? Re: eps:: 1e-5 is AC, 1e-9 WA... you can try to find intersection point of lines x1,y1, x2,y2 x1+dt*cos(theta1),y1+dt*sin(theta1),x2+dt*cos(theta2), y2+dt*sin(theta2) x1=fx1+t*cos(theta1),y1=fy1+t*sin(theta1) x2=fx2+t*cos(theta2),y2=fy2+t*sin(theta2) point (fx1,fy1) and (fx2,fy2) is the point on the convex polygon you can the intersection point x(t),y(t) by limit dt--->0 then length of args is sqrt((dx/dt)^+(dy/dt)^2) dt ,you can find the Primitive function of sqrt((dx/dt)^+(dy/dt)^2) and compute the integral by O(1) |
|
|