I got WA #4, but I think I got all special cases ok, so help please.

I think all problem is in looking, where the center of projectile is situated(outside or inside)...

I tryied to find the diameter with binary search and at each step we verify if it crosses the polygon.

I used different approach, first I calculate if the center is inside, using dummy point ( point that is inside ), and then I calculate minimum distance to the from then center to the polygon, my code:

[code deleted]

Edited by moderator 13.02.2007 20:51

Here is a test for you:
-1000000 1000000 4
0 -1000
600 0
0 1000
-1000 0

mine says: 2827012.911
yours: 2827013.265

little diference but...
You can implement the binary search, it's easy... And then compare it with your solution to find the bug...

I have the same solution and it gives the same answer to the offered test. It is mathematically proved that the algo is correct.
Thus, the difference from right answer appears only because of computer limitations. It means we should try to guess the author's solution (according to which the tests were created) and throw away all other correct ones (this, for example).
It's completely unfair.

3 0 8
0 2
2 0
4 0
6 2
6 4
4 6
2 6
0 4

[0.000]

0 0 8
0 2
2 0
4 0
6 2
6 4
4 6
2 6
0 4

[2.828]

0 0 4
1 1
-1 1
-1 -1
1 -1

[0.000]

-1000000 -1000000 3
999999 1000000
1000000 999999
1000000 1000000

[5656852.835]

2 0 3
4 0
3 3
0 3

[2.400]

try this test....
0 0 3
1 0
3 0
2 3
-> 2.000

Why do you write such tests? Coordinates must be in range [-2000, 2000]

Edited by author 08.07.2014 06:09