So, there are precision problems. It it will help someone, here is the test:
100000000 100000000
0 0 1 0 1 1
0 99999999
1
0 99999998 100000000 99999998 100000000 99999999

Answer is -1.

Edited by author 21.06.2008 14:14

Problem very complex
I think that some trace of helpful tests very needed
My first troubles was in test 4
and traing test 100 100 2 10 1 3 3 3 10 1 1 6 8 5 7 7 7
answer:-1
helped.
Test 5- first for which N>1
I passed test 5,6 with help of
19 19 1 18 0 17 2 17 7 16 2 5 18 3 1 7 1 7 19 6 17 8 17
answer:36.895
for test 7 we must rewrite all geometric procedures in __int64 mode
after that I jumped to test17 and have VA17
two test on the way:
10 10 1 1 0 0 2 0 7 7 2 6 9 4 0 6 0 7 7 8 7 8 6
answer=18.506
10 10 1 1 0 0 2 0 7 7 2 6 9 4 0 6 0 7 7 8 7 8 5
answer=-1
for tests 1-16 N>0, all triangles have square > 0,
initial and final points are different.
also:main idea works:
optimal path goes between corners of forbidden zones
which are convex 4-9 poligones(Minkowski sums)
and Floid applicable
what to do?
my convex hull utilita uses inside double-value
considirations. It is helpful to find
pure int convex_hull utilita
It became easy and I jumped to test 29.
Interesting that I did not sense that tests 16 and 22
very tricky!
In test 29 N==0, remove "заглушка" go forward! AC-0.89!
Resume: problem is not most difficult in timus,
thank to authorth, ships is not degenerated in all tests.
How speed up: to use Dejkstra instead of Floid!
Religion:Using float in geometric problems leeds
often to Wa during a long time and may made us seek.

Made Dejkstra!Two position up to 0.765AC.
It doesn't the matter.
Main reserve: to speed up subroutine:
verify that segment with int ends intersects with
convex poligon(it's inner part).


Edited by author 10.03.2008 20:18

Yes, this problem is REALLY superior! I was forced to use __int64-calculations to avoid error in precision, so 0.921 sec. There is 10 tasks in one! #1271 is the best on Timus!

You are a lol and an idiot!
You used a dirty account...