A first remark is that no one succeeded in solving the problem up to its
end, the only ones who were close to it are **Ioana Ileana** (7 tests out of
8), **Dumitru Bogdan** and **Cadar Cristian** (6 tests out of 8).
Let's analyse the complexity of the program. As the number of crossings and
roads is at the most 5001, we deduct that the complexity - so that the program
might fit in one second's time - should have been of the form
`n*log(n)`.
Before presenting the algorithm, I must specify that no order was requested
as far as the belts' order is concerned (that is the first belt of the city and
then the rest of them, or any other order), as we didn't want to make the
program too complicated.
The problem confines to finding out the faces of a planar graph. Let n be
the number of points (vertexes) and m the number of edges of a graph. The
number of faces is given by the formula:
m-n+the_number_of_connected_components+1

(1 is added for the exterior face). But the graph is connected, so the formula
becomes `m-n+2`. One edge appears in exactly two faces. If the
edge is divided into two orientated arcs, then you can make it so that each arc
appears in only one face. To find the belts, you must start on some arc (chosen
at random) from a point (vertex) and continue traversing the graph on the arc
that forms the smallest angle with the arc you came on.
A belt is made when the starting point is reached. All the arcs through
which you passed are erased from the list. All the belts are made when the
graph becomes void.
There were given **8** tests, each one scored at **3.75** points. The
score was rounded.