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 1664. Pipeline Transportation

LSBG what are the coordinates for? [8] // Problem 1664. Pipeline Transportation 20 Dec 2008 14:42
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.
Sandro (USU) Re: what are the coordinates for? [2] // Problem 1664. Pipeline Transportation 22 Dec 2008 11:51
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.
Tbilisi SU: Giorgi , Akaki , [Andrew] Re: what are the coordinates for? [1] // Problem 1664. Pipeline Transportation 25 Dec 2008 15:09
I wrote this problem one year before , with standart maxflow algorithm , and got AC during the contest.
Tbilisi SU: Giorgi , Akaki , [Andrew] Re: what are the coordinates for? // Problem 1664. Pipeline Transportation 25 Dec 2008 15:55
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.
Jedi Knight Re: what are the coordinates for? [1] // Problem 1664. Pipeline Transportation 31 Mar 2010 22:28
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