ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1853. Laser Technologies

eps:: 1e-5 is AC, 1e-9 WA...
Posted by Shen Yang 23 Feb 2017 12:05
RT
Re: eps:: 1e-5 is AC, 1e-9 WA...
Posted by Ilya Shuvaloff 28 Feb 2017 14:42
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...
Posted by Shen Yang 28 Feb 2017 15:57
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)