I can't understand what do we need the plain coordinates for.

Edited by author 20.12.2008 14:48

For nothing I think.
I absolutely ignored coords, used standard Maxflow and got TLe13 because of 0.5 sec. Main point is speed.

There are 2 different ways to solve this problem. The first one is to optimize one of the standard Maxflow algorithms to pass TL. The second one is to use the planarity of graph, design an algorithm that is asymptotically faster than the standard ones, and get AC with it.

I wrote this problem one year before , with standart maxflow algorithm , and got AC during the contest.

here I got TLE :|

Exuse me!.Brilliant the problem, thank the authors.
We build dual graph and use Dejkstra in it- O(nlog(n)).
But computing dual graph is separated difficult problem
from computational geometry connected with walking on grid
with extacting faces.

Now I am implementing this approach.
In test 14 I have situation when starting from some
edge and making maximal possible turn to left we don't
return to starting edge. Is it possible in
comlex geometry or bug in program.

Edited by author 18.07.2009 11:05

I've implemented svr's approach and it seems to be the fastest one.
I had a lot of problems with my program, but not on test 14 or 15.
But I have overcome WA#16 when replaced atan2 with exact geometry.

Found: test 14 contains edge with only one facet :)

I also have implemented it.
Dual graph making is not very easy.
But strength (n*log(n)) of this method is great.
I used set,vector and had not TL.

Edited by author 19.12.2011 12:22