Олимпиадный тренинг

Задача . Three Lines


Задача

Темы: жадные алгоритмы

Фермер Джон хочет отслеживать свои N коров (1 <= N <= 50,000), используя свою новую систему наблюдения, которую он купил.
I-ая корова расположена в позиции (xi, yi) с целочисленными координатами (в диапазоне 0...1,000,000,000); никакие две коровы не расположены в одной и той же позиции.
Система наблюдения ФД имеет три специальные камеры, каждая из которых способна отслеживать всех коров вдоль некоторой вертикальной или горизонтальной оси. Пожалуйста, помогите ФД определить, возможно ли установить эти три камеры так, чтобы отслеживать всех его коров. То есть, Определите, могут ли все N позиций коров быть покрыты некоторым множеством из трех прямых, каждая из которых ориентирована горизонтально или вертикально.
Замечание: программы, которые не делают ничего, кроме угадывания ответа, могут быть дисквалифицированы.
PROBLEM NAME: 3lines
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит разделенные пробелом целые числа xi yi , определяющие положение коровы i.
Формат выходных данных
* Строка 1: Выведите 1, ели возможно отслеживать всех коров тремя камерами и выведите 0 в противном случае.
Примечание
Прямые y=0, x=1, y=4 отслеживают все N коров.
Примеры
№Входные данныеВыходные данные
1 
6
1 7
0 0
1 2
2 0
1 4
3 4
 
1
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет