This problem was actually proposed in one of the latest Codeforces rounds. It is obvious that the Greedy algorithm is not good enough. The trick is to make a bipartite graph with the X-s coordinates of the points in one set and the Y-s in the other. Then we can add undirected edges from any x from the first set to any y from the other set as long as point (x,y) exists in input. If our resulting graph is eulerian, it's obvious that our problem is done, because we can color edges ( that are actually points from the input ) in white-red-white-red uniformly across the eulerian cycle we have. The problem is if we have nodes with odd degree. That can be really nice solved by adding 2 more nodes, one where we add edges between him and the x's nodes with odd degree and other node where we add between him and the y's nodes with odd degree. The question is : What if these 2 other nodes have odd degree now? We can easily notice that either both have odd degree , either both have even degree, so it is enough to add an edge between them in case the degrees are odd. And we have an eulerian graph. In this way, after coloring the eulerian path as I sad, every node has an equal number of white and red edges adiacent to him, so if we delete our fake 2 nodes we used to help us, the difference of colors is at most 1, and the problem is solved.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena