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

Обсуждение задачи 1768. Кольцевые струны

Test 18
Послано bsu.mmf.team 16 апр 2010 00:01
What the fucking test is it? I failed on it many times, using every possible precision in calculations!
Re: Test 18
Послано Igor9669 16 апр 2010 00:31
I used Eps=1E-7 to compare two numbers and got Ac.
Re: Test 18
Послано bsu.mmf.team 17 апр 2010 01:43
I used it too...

By the way, maybe my algo is wrong? I calculated the distances between i-th and (i+1)-th poitns and the distances between i-th and ((i+n/2) mod n)-th points if n is even or between i-th and a middle of segment, which is constructed by ((i+(n-1)/2) mod n)-th and ((i+(n+1)/2) mod n)-th points if n is odd. If these distances are equal, then "YES"

Edited by author 17.04.2010 01:44
Re: Test 18
Послано Igor9669 17 апр 2010 01:49
maybe it is wrong!))
Re: Test 18
Послано bsu.mmf.team 17 апр 2010 02:07
OK, what counter-test do you know then? :)
Re: Test 18
Послано Igor9669 17 апр 2010 12:52
what will be your answer if the polygon is not convex??
Re: Test 18
Послано bsu.mmf.team 17 апр 2010 14:14
Oh! You are right, my program outputs "YES" on some special tests, but the answer should be always "NO"! Thank you!

Now I've got AC. Simple algo with checking if points lie on a circumference and Point[i].x = x0 + R*cos(a0 + 2*k*PI/n), Point[i].y = y0 + R*sin(a0 + 2*k*PI/n) is true for sure.
I just wanted to implement my "exotic" algo there :))))
But it was wrong...

Edited by author 18.04.2010 12:11
Re: Test 18
Послано xt3000 25 апр 2010 12:57
I used your algo,but always wa4 ,why?
Re: Test 18
Послано SuperLight 25 апр 2010 13:01
Re: Test 18
Послано SuperLight 25 апр 2010 13:53
Re: Test 18
Послано svr 24 окт 2010 11:27
I think that most Ac are by the chance, varing eps.
If impossible to solve from the fist submission the problem is incorrect.
I think right uderstanding the problem is following:
Let P=<P1,...,Pn>-given n-polygon and
r(P)=min(max dist(Pi-Qi),on all ideal n-polygons Q=<Q1,...,Qn>)
if(r(P)<=1.e-5) YES else NO.
That is optimization problem.

P.S. I glad to say that under above consideration
I got AC immidiately,
while using chaotic eps-using had 12 WA 18.

Edited by author 24.10.2010 12:41