Farmer John muốn giám sát \(N\) con bò của mình (\(1 \le N \le 50\,000\)) bằng một hệ thống giám sát mới mua.

Con bò thứ \(i\) nằm tại vị trí \((x_i, y_i)\) với tọa độ nguyên (trong khoảng từ 0 đến \(1\,000\,000\,000\)); không có hai con bò nào ở cùng một vị trí. Hệ thống giám sát của FJ gồm ba camera đặc biệt, mỗi camera có khả năng quan sát tất cả những con bò nằm trên một đường thẳng đứng hoặc một đường nằm ngang. Hãy xác định liệu FJ có thể bố trí ba camera này để giám sát tất cả \(N\) con bò hay không. Nói cách khác, hãy xác định liệu toàn bộ \(N\) vị trí của đàn bò có thể đồng thời được "phủ" bởi một tập hợp gồm ba đường thẳng, mỗi đường có phương nằm ngang hoặc thẳng đứng hay không.

Lưu ý: Những chương trình không làm gì ngoài việc đoán ngẫu nhiên dữ liệu ra có thể bị loại và nhận số điểm bằng không.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa hai số nguyên \(x_i\) và \(y_i\), cách nhau bởi dấu cách, cho biết vị trí của con bò \(i\).

Dữ liệu ra

• Dòng 1: In ra 1 nếu có thể giám sát tất cả \(N\) con bò bằng ba camera; nếu không, in ra 0.

Ví dụ

6
1 7
0 0
1 2
2 0
1 4
3 4

1

Nguồn

USACO 2012 US Open, Bronze Division — Three Lines

Tác giả: Brian Dean, 2012.