Park tour

All submissions for this problem are available.
Imagine a large nxn square park composed of small unit squares. Some squares are occupied by trees, and the rest is free to walk through them. Your job is to create a visiting route which should be as long as possible. The route should be a closed curve with no selfintersections, and is defined by describing the sequence of squares through which it passes. From one square, the route can only proceed to a square which shares a common edge with it. The route enters and leaves each square in the central points of two of its edges. If those two points lie on opposing edges of the square (N  S or E  W), the fragment of the route within the square is a straight line segment of length l=1. Otherwise, if the two points lie on adjacent edges, the route within the square is an arc of the circle (1/4th of the full circle of radius 1/2, centered at the common corner of the edges) and its length is l=pi/4.
Input
In the first line of input there is an integer n (100≤n≤800), denoting the size of park. The following n lines of n characters each describe the park: the character '*' represents a square with a tree, and the character '.' means that the square is empty.
Output
First, an integer k (0<k), corresponding to the number of lines of the subsequent description of the output. The following k pairs of numbers should describe the squares of the route: i_{1},j_{1} ... i_{k},j_{k}, where i is the row number (counting from 0) and y is the column number (counting from 0) of a square.
Correctness of the output
For each i<k, squares i and i+1 of the route should share a common edge, and moreover the first and the kth squares should also share a common edge. The route may not make a Uturn at any square, and may not lead through any squares with trees. The route should not selfintersect or touch itself. The route is not allowed to lead outside the park. Note that it is possible for the route to be twice in the same square (i.e. once enter from N exiting due E, later enter from S exiting due W).
Example
Input: 3 ..* ... *.. Output: 8 0 0 0 1 1 1 1 2 2 2 2 1 1 1 1 0 Score: 0.897598
Test distribution
n will be chosen uniformly from the range [100,800] range. The number of trees will be chosen uniformly from the range [n^{2}*alfa,n^{2}*2*alfa), where alfa = 0.1 for 1/3 of the testcases, alfa = 0.02 for 1/3 of the testcases, and alfa = 0.004 for 1/3 of the testcases. Positions of trees are chosen uniformly at random.
Scoring
The score is given as l / f, where l is the total length of the route and f is the total number of squares without trees.
Author:  admin 
Tags  admin 
Date Added:  30110001 
Time Limit:  10 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, SQL, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions