ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1853. Лазерные технологии

eps:: 1e-5 is AC, 1e-9 WA...
Послано Shen Yang 23 фев 2017 12:05
RT
Re: eps:: 1e-5 is AC, 1e-9 WA...
Послано Ilya Shuvaloff 28 фев 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...
Послано Shen Yang 28 фев 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)