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 1768. Circular Strings

2 admins - 2
Posted by DK [Samara SAU] 11 Apr 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
Posted by Burunduk1 11 Apr 2010 18:06
Why do you think so?
Do you mean there is no n-gons for n != 4 ? :)
Re: 2 admins - 2
Posted by Al.Cash 11 Apr 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
Posted by DK [Samara SAU] 11 Apr 2010 19:36
Not, all is not OK cause to program with absolute precision will fail with WA.
Re: 2 admins - 2
Posted by DK [Samara SAU] 11 Apr 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
Posted by Burunduk1 11 Apr 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
Posted by DK [Samara SAU] 12 Apr 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
Posted by DK [Samara SAU] 12 Apr 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
Posted by bsu.mmf.team 14 Apr 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
Posted by Kain 18 Apr 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
Posted by olpetOdessaONU [1 2/3] 26 Oct 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.