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

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

2 admins - 2
Послано DK [Samara SAU] 11 апр 2010 18:03
your 8h test is incorrect, the answer is ALWAYS NO if n != 4
if u contact me, I'll give you the prove
Re: 2 admins - 2
Послано Burunduk1 11 апр 2010 18:06
Why do you think so?
Do you mean there is no n-gons for n != 4 ? :)
Re: 2 admins - 2
Послано Al.Cash 11 апр 2010 19:17
Regular n-gons with n != 4 can't have all vertixes with rational coordinates.
But it's said in the statement that coordinates are given with some accuracy, so I think it's ok.
Re: 2 admins - 2
Послано DK [Samara SAU] 11 апр 2010 19:36
Not, all is not OK cause to program with absolute precision will fail with WA.
Re: 2 admins - 2
Послано DK [Samara SAU] 11 апр 2010 19:39
there are some problems like this:
4
0 0
0 1
1 1
1 0
//YES, obviously

4
0 0.000009
0 1
1 1
1 0
//YES or incorrect test due to 10^-5 restriction?!

4
0 0.00000000000000000000000000009
0 1
1 1
1 0
//YES or incorrect test due to 10^-5 restriction?!
Re: 2 admins - 2
Послано Burunduk1 11 апр 2010 19:45
In the statement you may see two numbers: 10^{-5}, 10^{-10}

So about your tests:
The first, you are right, is YES, obviously.
The second does not exist (By the statement, there are no such tests in testset!)
The third is same to the first.
Re: 2 admins - 2
Послано DK [Samara SAU] 12 апр 2010 03:48
why is 10^{-10} a minimal guarantees for 'YES' answer?
this is just input precision.

Edited by author 12.04.2010 03:49
Re: 2 admins - 2
Послано DK [Samara SAU] 12 апр 2010 13:01
I think that statement need an additional guarantee like

"It is guaranteed that in the case of the positive answer the coordinates of the points can be changed by less than 10^(−10) [or another magic constant from jury solution] so that they become the coordinates of vertices of a regular n-gon written in the traversal order"
Re: 2 admins - 2
Послано bsu.mmf.team 14 апр 2010 04:08
For example, test:

5
1 0.5
0.654508, 0.975528
0.0954915, 0.793893
0.0954915, 0.206107
0.654508, 0.0244717

The answer is "YES" !!!
Re: 2 admins - 2
Послано Kain 18 апр 2010 11:34
Try this interesting test:
4
0 0.333333
0.5 0.666667
1 0.333333
0.5 0
The answer is NO.

Edited by author 18.04.2010 11:57
Re: 2 admins - 2
Послано olpetOdessaONU [1 2/3] 26 окт 2011 00:34
I think, that answer on this test:

4
0.0000199999 0.0000100000
0.0000000001 0.9999900000
0.9999999999 0.9999900000
0.9999800001 0.0000100000

is YES
for example, the resulting points are

0.00001 0.00001
0.00001 0.99999
0.99999 0.99999
0.99999 0.00001

but my AC program answers NO

And I still think that this problem is much more hard, that author thinks, because of different precisions in the statement.