423. Четыре точки

Не решаласьСложная

На плоскости задано n n попарно различных точек c целочисленными координатами. Необходимо проверить, существуют ли среди них четыре точки, образующие вершины выпуклого четырёхугольника.

Формат ввода

В первой строке дано одно целое число n n — количество точек ( 4 ≤ n ≤ 100   000 4 \le n \le 100\ 000 ). Последующие n n строк содержат по два целых числа x i x_i , y i y_i ( – 1 0 9 ≤ x i , y i ≤ 1 0 9 –10^9 \le x_i, y_i \le 10^9 ) — координаты очередной точки на плоскости. Гарантируется, что все точки попарно различны.

Формат вывода

В единственной строке выведите Yes, если существуют такие четыре точки, иначе выведите No.

Примечание

Четырехугольник - это геометрическая фигура (многоугольник), состоящая из четырёх точек (вершин), никакие три из которых не лежат на одной прямой, и четырёх отрезков (сторон), последовательно соединяющих эти точки.

Многоугольник является выпуклым, если он лежит только в одной полуплоскости для каждой прямой, содержащей его сторону.

Ограничения

Ограничение времени
2 с
Ограничение памяти
512 МБ

Примеры

Пример 1

Ввод
4
0 0
1 0
3 1
0 1
Вывод
Yes

Пример 2

Ввод
5
0 1
0 2
0 3
0 4
0 5
Вывод
No

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти