ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Шпалы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— Метростроевцы не ангелы. Они и работают под землёй, да и вообще… Ну не ангелы. А где вы их, ангелов-то, видали? Я ведь это все к чему: ну с кем не бывает? Вы мне покажите сначала, кто тут такой весь беленький-чистенький, а потом уж… Все ведь люди. И мы с Васей тоже. Ну может чуть сверх меры приняли. Дак ведь совсем чуть-чуть. И то, что шпалы немного криво лежат… Тогда-то казалось, что ровно. Нет, конечно, нельзя сказать, что так и должно быть — что они крест-накрест, ну да ведь не все крест-накрест! Некоторые, вон почти нормально лежат… Криво говорите? А мне кажется, нормально… После вчерашнего? Ну может быть, может быть… Да просто те, что крест-накрест лежат, уберём сейчас, и все нормально, и поезд в срок пойдёт, не к этому Новому году, так к следующему. Да немного разбирать! Вот эту выдернуть, и может эту вот ещё. Всего-то ничего. Одну, две, три…
Рельсы суть две параллельные прямые, которые, для удобства пользователей, параллельны оси 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 года
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1273. Шпалы