ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Tie

Time limit: 1.0 second
Memory limit: 64 MB
The subway constructors are not angels. The work under the ground and… Well, they are not angels. And where have you seen angels? It is all in a lifetime! Show me first somebody who has never… and then… all of us are people. And Vasya and me, too. May be we’ve overdrunked ourselves. But a little. And the ties lie crookedly… At that time they seemed to lie straight. No, we can’t say that it must be so — criss-cross, but not all of them criss-cross! Some of the ties lie almost properly… Crookedly you say? And I’d say normally… After the yesterday’s party? May be, may be… The ties that lie criss-cross we’ll take away and it’ll be OK, the train will pass on term, not by this New Year but by the next one. There’s not much to disjoint. We’ll pull out this tie and may be that one. Next to nothing! One, two, three…
Rails are two parallel straight lines that are for the users’ accommodation parallel to the Y axis and have the coordinates X=0 and X=1. The “pell-mell” ties are arbitrary segments with the vertices on the rails in the integer points of the coordinate scale. At the first elimination of defects step you are to remove several ties that would disappear all the crossings. And, of course, after the yesterday’s party the less you work the better, so you are to remove the minimal possible number of ties.


The first line contains integer K (0 ≤ K ≤ 100) — the number of laid ties. Then there are K lines, each of them contains two integers Y1 and Y2 that describe the location of the next in turn tie — the tie described by the pair Y1 and Y2 connects the points (0, Y1) и (1, Y2). The absolute values of the numbers Y1 and Y2 don’t exceed 1000. There are no identical among the numbers Y1 and among the numbers Y2.


the minimal number of ties that are to be removed in order to eliminate crossings.


0 1
3 0
1 2
Problem Author: Magaz Asanov (prepared Leonid Volkov)
Problem Source: Ural State University championship, October 25, 2003
To submit the solution for this problem go to the Problem set: 1273. Tie