My question is about one problem given in last round of codeforces, pretty easy to handle it, but I do not understand the other players` solutions.
We have a convex polygon and numbers it's vertices 1, 2, ..., n in clockwise order. Then starting from the vertex 1 , we draw a ray in the direction of each other vertex. The ray stops when it reaches a vertex or intersects with another ray drawn before. We repeat this process for vertex 2, 3, ..., n (in this particular order). And then we put a walnut in each region inside the polygon. What is the minimum number of jumps we have to perform in order to collect all the walnuts?
I think the answer is equivalent to find the number of all those distinct regions / faces of that graph.
How could the answer be: $(n−2)^2$.
One way to count the regions is to ask how many lines get drawn, and then add one (since we started with a single region). Vertex 0 will draw lines to $n-3$ other vertices (all but $0$, $1$ and $n-1$), and will actually reach them, so no other vertices will draw lines toward $0$. Thus, a subsequent vertex $k$ draws lines in the directions of everyone but $k-1$, $k$, $k+1$ and $0$, where addition is mod $n$.
That means vertices $0$, $1$ and $n-1$ draw $n-3$ lines each, and the remaining $n-3$ vertices draw $n-4$ lines each, for a total of $$3(n-3)+(n-3)(n-4)=(n-3)(n-1)=(n-2)^2-1$$ lines, hence $(n-2)^2$ regions.
The rules state you're allowed to "jump" between regions which share a side or a corner, which makes it easy to find a route: every region touches an original vertex, so just follow the original $n$-gon around in vertex order.
If you're careful, you can do this in a way which only uses edge-adjacencies (i.e. you don't do any corner-hops around regions meeting at a corner.). But that's more than was asked.