Một công viên gần đó có \(n\) đài phun nước, được đánh số từ \(0\) đến \(n-1\). Ta mô hình hóa các đài phun nước bằng các điểm trên mặt phẳng tọa độ hai chiều. Cụ thể, đài phun nước \(i\) (\(0 \le i \le n-1\)) là điểm \((x[i], y[i])\), trong đó \(x[i]\) và \(y[i]\) là các số nguyên chẵn. Vị trí các đài phun nước đôi một khác nhau.

Kiến trúc sư Timothy được thuê để lên kế hoạch xây dựng một số con đường và bố trí một ghế đá cho mỗi con đường. Mỗi con đường là một đoạn thẳng nằm ngang hoặc thẳng đứng, có độ dài \(2\), với hai đầu mút là hai đài phun nước khác nhau. Các con đường phải được xây dựng sao cho có thể đi lại giữa hai đài phun nước bất kỳ bằng cách di chuyển dọc theo các con đường. Ban đầu, công viên không có con đường nào.

Với mỗi con đường, cần đặt đúng một ghế đá trong công viên và gán ghế đá đó cho con đường (nghĩa là ghế quay mặt về phía con đường). Mỗi ghế đá phải được đặt tại một điểm \((a, b)\) sao cho \(a\) và \(b\) là các số nguyên lẻ. Vị trí các ghế đá phải đôi một khác nhau. Một ghế đá tại \((a, b)\) chỉ có thể được gán cho một con đường nếu cả hai đầu mút của con đường đều thuộc tập hợp:

Ví dụ, ghế đá tại \((3,3)\) chỉ có thể được gán cho một con đường là một trong bốn đoạn thẳng \((2,2)\)–\((2,4)\), \((2,4)\)–\((4,4)\), \((4,4)\)–\((4,2)\), \((4,2)\)–\((2,2)\).

Hãy giúp Timothy xác định liệu có thể xây dựng các con đường, đặt và gán các ghế đá thỏa mãn tất cả các điều kiện trên hay không. Nếu có, hãy đưa ra một phương án hợp lệ. Nếu có nhiều phương án thỏa mãn tất cả các điều kiện, bạn có thể đưa ra bất kỳ phương án nào.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int construct_roads(std::vector<int> x, std::vector<int> y);

• x, y: hai mảng độ dài \(n\). Với mỗi \(i\) (\(0 \le i \le n-1\)), đài phun nước \(i\) là điểm \((x[i], y[i])\), trong đó \(x[i]\) và \(y[i]\) là các số nguyên chẵn.
• Nếu có phương án xây dựng hợp lệ, hàm phải gọi build (xem dưới đây) đúng một lần để báo cáo phương án, sau đó trả về \(1\).
• Nếu không, hàm phải trả về \(0\) mà không gọi build.
• Hàm này được gọi đúng một lần.

Chương trình của bạn có thể gọi hàm sau để đưa ra một phương án xây dựng đường và bố trí ghế đá hợp lệ:

void build(std::vector<int> u, std::vector<int> v,
           std::vector<int> a, std::vector<int> b);

• Gọi \(m\) là tổng số con đường trong phương án xây dựng.
• u, v: hai mảng độ dài \(m\), biểu diễn các con đường cần xây dựng. Các con đường được đánh số từ \(0\) đến \(m-1\). Với mỗi \(j\) (\(0 \le j \le m-1\)), con đường \(j\) nối hai đài phun nước \(u[j]\) và \(v[j]\). Mỗi con đường phải là một đoạn thẳng nằm ngang hoặc thẳng đứng có độ dài \(2\). Hai con đường khác nhau bất kỳ có nhiều nhất một điểm chung (là một đài phun nước). Sau khi xây dựng, phải có thể đi lại giữa hai đài phun nước bất kỳ bằng cách di chuyển dọc theo các con đường.
• a, b: hai mảng độ dài \(m\), biểu diễn các ghế đá. Với mỗi \(j\) (\(0 \le j \le m-1\)), một ghế đá được đặt tại \((a[j], b[j])\) và được gán cho con đường \(j\). Không có hai ghế đá khác nhau nào cùng vị trí.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2+i\) (\(0 \le i \le n-1\)): \(x[i]\ y[i]\).

Dữ liệu ra

Trình chấm mẫu in kết quả theo định dạng sau:

• Dòng \(1\): giá trị trả về của construct_roads.

Nếu construct_roads trả về \(1\) và build(u, v, a, b) được gọi, trình chấm mẫu in thêm:

• Dòng \(2\): \(m\).
• Dòng \(3+j\) (\(0 \le j \le m-1\)): \(u[j]\ v[j]\ a[j]\ b[j]\).

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(2 \le x[i], y[i] \le 200\,000\) với mọi \(0 \le i \le n-1\).
• \(x[i]\) và \(y[i]\) là các số nguyên chẵn với mọi \(0 \le i \le n-1\).
• Không có hai đài phun nước nào cùng vị trí.

Phân nhóm

Ví dụ

construct_roads([4, 4, 6, 4, 2], [4, 6, 4, 2, 4])

1

build([0, 0, 3, 4], [2, 1, 0, 0], [5, 3, 5, 3], [5, 5, 3, 3])

build([1, 2, 3, 4], [0, 0, 0, 0], [5, 5, 3, 3], [5, 3, 3, 5])

construct_roads([2, 4], [2, 6])

0

Nguồn

IOI 2021, Ngày 1 — Fountain Parks (parks).