Đường Biên Ngoài Cùng · canuc80k6905

Cho $n$ điểm phân biệt trên mặt phẳng. Bao lồi của tập điểm là đa giác lồi nhỏ nhất chứa tất cả các điểm đã cho.

Hãy in toàn bộ những điểm đã cho nằm trên biên của bao lồi. Một điểm nằm giữa hai đỉnh cực trị trên cùng một cạnh cũng thuộc biên và bắt buộc phải được in.

Input

Dòng đầu chứa số nguyên $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x, y$ - tọa độ một điểm.

Output

Dòng đầu in số nguyên $k$ - số điểm nằm trên biên bao lồi.
Tiếp theo in $k$ dòng, mỗi dòng là tọa độ một điểm biên. Các điểm có thể được in theo bất kỳ thứ tự nào, nhưng mỗi điểm phải xuất hiện đúng một lần và không được in điểm nằm trong.

Constraints

$3 \leq n \leq 2 \cdot 1 0^{5}$ .
$- 1 0^{9} \leq x, y \leq 1 0^{9}$ .
Các điểm đôi một khác nhau.
Bao lồi có diện tích dương, tức là không phải mọi điểm đều thẳng hàng.

Scoring

Subtask $1$ ( $50$ điểm): $n \leq 50$ và trị tuyệt đối mọi tọa độ không quá $100$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Sáu điểm được in nằm trên bốn cạnh của hình chữ nhật bao ngoài, trong đó $(2, 0)$ và $(2, 3)$ nằm giữa hai góc nhưng vẫn thuộc biên. Ba điểm còn lại nằm nghiêm ngặt bên trong nên không được in.

Ý tưởng: Sắp xếp các điểm theo cặp $(x, y)$ . Ta xây biên dưới từ trái sang phải: sau khi thêm một điểm, nếu ba điểm cuối tạo một bước ngoặt phải thì điểm ở giữa không thể nằm trên biên dưới và được loại. Biên trên được xây tương tự khi duyệt từ phải sang trái.
Ý tưởng: Điểm quan trọng của bài là phải giữ các điểm thẳng hàng trên cạnh bao. Vì vậy vòng lặp chỉ loại khi tích có hướng âm; nếu tích bằng $0$ , điểm giữa vẫn được giữ. Sau khi bỏ hai đầu mút bị lặp và ghép hai chuỗi, ta thu được đúng toàn bộ tập điểm biên.
Ý tưởng: Sắp xếp tốn $O (n lo g n)$ thời gian, hai lượt quét tốn $O (n)$ và bộ nhớ là $O (n)$ . Tích có hướng dùng số nguyên 128 bit.