— Метростроевцы не ангелы. Они и работают под землёй, да и вообще… Ну не ангелы. А где вы их, ангелов-то, видали? Я ведь это все к чему: ну с кем не бывает? Вы мне покажите сначала, кто тут такой весь беленький-чистенький, а потом уж… Все ведь люди. И мы с Васей тоже. Ну может чуть сверх меры приняли. Дак ведь совсем чуть-чуть. И то, что шпалы немного криво лежат… Тогда-то казалось, что ровно. Нет, конечно, нельзя сказать, что так и должно быть — что они крест-накрест, ну да ведь не все крест-накрест! Некоторые, вон почти нормально лежат… Криво говорите? А мне кажется, нормально… После вчерашнего? Ну может быть, может быть… Да просто те, что крест-накрест лежат, уберём сейчас, и все нормально, и поезд в срок пойдёт, не к этому Новому году, так к следующему. Да немного разбирать! Вот эту выдернуть, и может эту вот ещё. Всего-то ничего. Одну, две, три…
Рельсы суть две параллельные прямые, которые, для удобства пользователей, параллельны оси Y и имеют координаты X=0 и X=1. Шпалы «после вчерашнего» — это произвольные отрезки с вершинами на рельсах, в целых точках координатной сетки. На первом этапе устранения допущенных при укладке шпал небольших неточностей необходимо удалить несколько шпал так, чтобы, по крайней мере, исчезли все пересечения. Ну и, конечно, работать-то после вчерашнего хочется поменьше, поэтому желательно удалять как можно меньше шпал.
Исходные данные
В первой строке входа находится целое число K (0 ≤ K ≤ 100) — количество уложенных шпал. Далее следует K строк, каждая из которых содержит два разделённых пробелом целых числа Y1 и Y2. Эти два числа описывают положение очередной шпалы — шпала, заданная парой чисел Y1 и Y2, соединяет точки (0, Y1) и (1, Y2). Все числа Y1 и Y2 по модулю не превышают 1000. Как среди чисел Y1, так и среди чисел Y2 нет одинаковых.
Результат
На выход следует подать единственное число — минимальное количество шпал, которое надо убрать, чтобы избавиться от пересечений.
Пример
исходные данные | результат |
---|
3
0 1
3 0
1 2 | 1 |
Автор задачи: Магаз Асанов (подготовил — Леонид Волков)
Источник задачи: Чемпионат Уральского государственного университета, 25 октября 2003 года