Azerbaijan nổi tiếng về thảm. Là một nhà thiết kế thảm bậc thầy, bạn muốn tạo ra một thiết kế mới bằng cách vẽ một đường gấp khúc. Một đường gấp khúc là một dãy gồm \(t\) đoạn thẳng trên mặt phẳng hai chiều, được xác định bởi một dãy \(t+1\) điểm \(p_0, \ldots, p_t\) như sau: với mỗi \(0 \leq j \leq t-1\), có một đoạn thẳng nối điểm \(p_j\) với điểm \(p_{j+1}\).

Để thực hiện thiết kế mới, bạn đã đánh dấu \(n\) dấu chấm trên mặt phẳng hai chiều. Tọa độ của dấu chấm \(i\) (\(1 \leq i \leq n\)) là \((x[i], y[i])\). Không có hai dấu chấm nào có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\).

Bây giờ bạn muốn tìm một dãy các điểm \((sx[0], sy[0]), (sx[1], sy[1]), \ldots, (sx[k], sy[k])\) xác định một đường gấp khúc thỏa mãn:

• Bắt đầu từ \((0, 0)\) (nghĩa là \(sx[0] = 0\) và \(sy[0] = 0\)).
• Chứa tất cả các dấu chấm (không nhất thiết phải tại các điểm đầu mút của các đoạn).
• Chỉ bao gồm các đoạn ngang hoặc dọc (hai điểm liên tiếp xác định đường gấp khúc có tọa độ \(x\) hoặc tọa độ \(y\) bằng nhau).

Đường gấp khúc được phép tự cắt hoặc chồng lên chính nó theo bất kỳ cách nào. Cụ thể, mỗi điểm trên mặt phẳng có thể thuộc vào một số lượng tùy ý các đoạn của đường gấp khúc.

Đây là bài toán chỉ nộp kết quả đầu ra (output-only) với cách tính điểm một phần. Bạn được cho \(10\) tệp đầu vào xác định vị trí của các dấu chấm. Đối với mỗi tệp đầu vào, bạn cần nộp một tệp đầu ra mô tả một đường gấp khúc thỏa mãn các yêu cầu. Đối với mỗi tệp đầu ra mô tả một đường gấp khúc hợp lệ, điểm của bạn phụ thuộc vào số đoạn trong đường gấp khúc (xem phần Cách tính điểm bên dưới).

Bạn không nộp mã nguồn cho bài toán này.

Khuôn dạng dữ liệu vào

Mỗi tệp dữ liệu vào có khuôn dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(1+i\) (với \(1 \leq i \leq n\)): \(x[i]\; y[i]\).

Khuôn dạng kết quả ra

Mỗi tệp kết quả ra phải có khuôn dạng sau:

• Dòng \(1\): \(k\) — số đoạn của đường gấp khúc.
• Dòng \(1+j\) (với \(1 \leq j \leq k\)): \(sx[j]\; sy[j]\).

Chú ý rằng dòng thứ hai phải chứa \(sx[1]\) và \(sy[1]\) (nghĩa là kết quả ra không chứa \(sx[0]\) và \(sy[0]\)). Mỗi \(sx[j]\) và \(sy[j]\) phải là số nguyên.

Ví dụ

4
2 1
3 3
4 4
5 2

6
2 0
2 3
5 3
5 2
4 2
4 4

Các ràng buộc

• \(1 \leq n \leq 100\,000\).
• \(1 \leq x[i], y[i] \leq 10^9\).
• Tất cả các giá trị của \(x[i]\) và \(y[i]\) đều là số nguyên.
• Không có hai dấu chấm nào có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\), nghĩa là \(x[i_1] \neq x[i_2]\) và \(y[i_1] \neq y[i_2]\) với \(i_1 \neq i_2\).
• \(-2 \cdot 10^9 \leq sx[j], sy[j] \leq 2 \cdot 10^9\).
• Kích thước của mỗi tệp được nộp (tệp kết quả đầu ra hoặc tệp nén ZIP) không được vượt quá 15 MB.

Cách tính điểm

Có \(10\) trường hợp kiểm thử được tính điểm, đánh số từ 01 đến 10. Mỗi trường hợp có điểm tối đa là \(10\), tổng cộng \(100\) điểm. Ví dụ 00 có \(0\) điểm.

Bạn nhận \(0\) điểm cho một trường hợp kiểm thử nếu kết quả đầu ra không xác định một đường gấp khúc thỏa mãn các yêu cầu. Ngược lại, điểm số được xác định bằng một dãy giảm \(c_1, \ldots, c_{10}\), thay đổi theo từng trường hợp kiểm thử.

Giả sử lời giải của bạn là một đường gấp khúc hợp lệ gồm \(k\) đoạn. Khi đó, bạn nhận được:

• \(i\) điểm, nếu \(k = c_i\) (với \(1 \leq i \leq 10\)).
• \(i + \dfrac{c_i - k}{c_i - c_{i+1}}\) điểm, nếu \(c_{i+1} < k < c_i\) (với \(1 \leq i \leq 9\)).
• \(0\) điểm, nếu \(k > c_1\).
• \(10\) điểm, nếu \(k < c_{10}\).

Dãy \(c_1, \ldots, c_{10}\) cho từng trường hợp kiểm thử được cho trong bảng sau. Các trường hợp từ 07 đến 10 dùng chung cột cuối.

Trình hiển thị

Gói đính kèm của bài toán có chương trình vis.py cho phép trực quan hóa các tệp đầu vào và đầu ra.

Để trực quan hóa một tệp đầu vào, sử dụng lệnh:

python vis.py [input file]

Bạn cũng có thể trực quan hóa lời giải của mình cho một tệp đầu vào bằng lệnh sau. Do các giới hạn kỹ thuật, trình hiển thị được cung cấp chỉ hiển thị \(1000\) đoạn đầu tiên của tệp kết quả đầu ra.

python vis.py [input file] --solution [output file]

Ví dụ:

python vis.py examples/00.in --solution examples/00.out

Nguồn: Đề thi chính thức IOI 2019, ngày thi thứ hai, bài Broken Line (line); bản tiếng Việt và bản Markdown của ban tổ chức, đối chiếu với gói đính kèm và bộ chấm chính thức.