BOI 2014 - Ngày 2

Hòn đảo Bytopia từng được trị vì trong một thời gian dài bởi vị vua công minh Byteasar. Sau khi nhà vua đột ngột qua đời, hai người con sinh đôi Biteon và Byteon không thể thống nhất ai sẽ lên ngôi. Họ quyết định chia hòn đảo thành hai tỉnh để cai trị riêng.

Trên bản đồ hình chữ nhật, hòn đảo có dạng một đa giác gồm \(N\) đỉnh. Mỗi cạnh của đa giác song song với một cạnh của bản đồ; hai cạnh liên tiếp luôn vuông góc. Các cạnh không cắt hay chạm nhau, ngoại trừ đầu mút chung của hai cạnh liên tiếp.

Biteon và Byteon muốn dùng đúng một đoạn thẳng nằm trong đa giác, song song với một cạnh của bản đồ, để chia hòn đảo thành hai đa giác bằng nhau. Hai đa giác được gọi là bằng nhau nếu có thể biến đổi đa giác này thành đa giác kia bằng một tổ hợp các phép đối xứng, quay và tịnh tiến. Tọa độ các đỉnh và hai đầu mút của đoạn chia đều phải là số nguyên.

Hãy xác định liệu có thể chia hòn đảo thành hai phần bằng nhau bằng một đoạn thẳng nằm ngang hoặc thẳng đứng hay không. Nếu có, hãy tìm một đoạn như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), số đỉnh của đa giác.

Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i,Y_i\), tọa độ đỉnh thứ \(i\).

Các đỉnh được cho theo thứ tự trên biên đa giác. Các cạnh là đoạn nối đỉnh \(i\) với đỉnh \(i+1\) với \(1 \le i<N\), cùng đoạn nối đỉnh \(N\) với đỉnh \(1\). Hai cạnh liên tiếp luôn vuông góc.

Dữ liệu ra

Nếu có cách chia hợp lệ với hai đầu mút \((x_1,y_1)\) và \((x_2,y_2)\), in bốn số nguyên \(x_1,y_1,x_2,y_2\) trên một dòng, cách nhau bởi dấu cách. Đoạn chia phải nằm ngang hoặc thẳng đứng, tức là \(x_1=x_2\) hoặc \(y_1=y_2\). Đoạn phải nằm trong đa giác và chỉ hai đầu mút của nó được chạm biên đa giác. Hai phần thu được phải là hai đa giác bằng nhau. Có thể in bất kỳ cách chia hợp lệ nào.

Nếu không có cách chia như vậy, in NO.

Ràng buộc

• \(4 \le N \le 100\,000\).
• \(0 \le X_i,Y_i \le 10^9\) với mọi \(1 \le i \le N\).
• Đa giác thỏa mãn các điều kiện hình học đã mô tả; hai đầu mút của đoạn chia phải có tọa độ nguyên.

Phân nhóm

1. 12 điểm: \(4 \le N \le 100\,000\). Mọi đường thẳng nằm ngang hoặc thẳng đứng chia cắt đa giác đều chia nó thành đúng hai phần.
2. 15 điểm: \(4 \le N \le 200\).
3. 23 điểm: \(4 \le N \le 2000\).
4. 50 điểm: \(4 \le N \le 100\,000\).

Ví dụ

10
0 0
1 0
1 1
3 1
3 5
2 5
2 3
1 3
1 2
0 2

1 2 3 2

6
0 0
1 0
1 1
2 1
2 2
0 2

NO

Trong mê cung có một chiếc bánh mà bạn rất muốn ăn. Bản đồ mê cung là một lưới gồm \(R\) hàng và \(C\) cột. Mỗi ô chứa một trong bốn ký tự:

• #: một khối tường.
• .: một ô trống.
• S: ô trống tại vị trí ban đầu của bạn.
• C: ô trống chứa chiếc bánh.

Bạn chỉ được đi trên các ô trống, và có thể đi từ một ô sang một ô trống có chung cạnh với nó. Toàn bộ vùng hình chữ nhật trên bản đồ được bao quanh bởi các khối tường.

Để đến chiếc bánh nhanh hơn, bạn có một khẩu súng tạo cổng của Aperture Science™. Bất kỳ lúc nào, bạn có thể bắn một cổng theo một trong bốn hướng lên, trái, xuống hoặc phải. Cổng bay theo hướng đó cho đến khi gặp khối tường đầu tiên, rồi xuất hiện trên mặt của khối tường hướng về phía bạn.

Tại mỗi thời điểm chỉ có tối đa hai cổng. Nếu đã có hai cổng, ngay khi bắn thêm một cổng, bạn phải chọn một trong hai cổng cũ để xóa. Bắn vào vị trí đang có cổng sẽ thay thế cổng đó: mỗi mặt của một khối tường có tối đa một cổng. Hai mặt khác nhau của cùng một khối tường có thể cùng chứa cổng.

Khi có hai cổng, bạn có thể dùng chúng để dịch chuyển. Đứng ở ô trống ngay cạnh một cổng, bạn có thể bước vào cổng đó và xuất hiện ở ô trống ngay cạnh cổng còn lại. Việc này mất thời gian bằng một bước đi giữa hai ô kề cạnh.

Việc bắn cổng không tốn thời gian. Mỗi bước đi giữa hai ô kề cạnh hoặc mỗi lần dịch chuyển qua cổng tốn một đơn vị thời gian.

Cho bản đồ mê cung, vị trí ban đầu và vị trí chiếc bánh, hãy tính thời gian ít nhất để đến chiếc bánh.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(R,C\), lần lượt là số hàng và số cột của bản đồ.

\(R\) dòng tiếp theo mô tả bản đồ; mỗi dòng gồm đúng \(C\) ký tự thuộc tập #, ., S, C. Mỗi ký tự S và C xuất hiện đúng một lần.

Dữ liệu ra

In một số nguyên: thời gian ít nhất để đi từ vị trí ban đầu đến chiếc bánh. Dữ liệu bảo đảm có thể đến được chiếc bánh.

Ràng buộc

• \(1 \le R,C \le 1000\).
• Có đúng một vị trí ban đầu và một vị trí chiếc bánh.
• Có thể đi từ vị trí ban đầu đến chiếc bánh.

Phân nhóm

1. 11 điểm: \(1 \le R \le 10\), \(1 \le C \le 10\).
2. 20 điểm: \(1 \le R \le 50\), \(1 \le C \le 50\).
3. 20 điểm: \(1 \le R \le 200\), \(1 \le C \le 200\). Mỗi ô trống có ít nhất một khối tường kề cạnh.
4. 19 điểm: \(1 \le R \le 200\), \(1 \le C \le 200\).
5. 30 điểm: \(1 \le R \le 1000\), \(1 \le C \le 1000\).

Ví dụ

4 4
.#.C
.#.#
....
S...

4

Năm 2036, người cao tuổi chiếm phần lớn dân số châu Âu. Để giúp họ duy trì sức khỏe, cơ quan phụ trách nhóm dân số này đề xuất giao cho họ việc phát lượng thư giấy ít ỏi còn được gửi, chủ yếu cũng dành cho người cao tuổi. Đề xuất sẽ được triển khai trên toàn châu Âu.

Châu Âu được chia thành các khu vực bưu chính. Mỗi khu vực có một mạng lưới gồm các con đường và giao lộ; mỗi con đường đều đi được theo hai chiều. Có thể thuê bao nhiêu người đưa thư trong mỗi khu vực tùy ý. Mỗi sáng, một người đưa thư nhận một túi thư để phát theo một hành trình đi qua một phần của mạng lưới.

Mỗi hành trình phải phù hợp với người cao tuổi, nghĩa là:

• Bắt đầu và kết thúc tại cùng một giao lộ.
• Không đi qua một giao lộ nhiều lần, ngoại trừ việc quay lại giao lộ xuất phát để kết thúc hành trình, nhằm tránh gây nhầm lẫn.
• Không có con đường chung với hành trình của người khác.

Các hành trình phải phủ toàn bộ mạng lưới: mỗi con đường thuộc đúng một hành trình.

Hãy tìm một tập hành trình thỏa mãn các điều kiện trên cho mạng lưới đường phố đã cho.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,M\), lần lượt là số giao lộ và số con đường. Các giao lộ được đánh số từ \(1\) đến \(N\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(u,v\), cho biết có một con đường nối giao lộ \(u\) với giao lộ \(v\).

Dữ liệu luôn thỏa mãn:

• \(1 \le u,v \le N\) và \(u \ne v\).
• Giữa hai giao lộ bất kỳ có nhiều nhất một con đường.
• Có thể đi từ giao lộ bất kỳ đến mọi giao lộ khác qua các con đường.
• Tồn tại một tập hành trình phù hợp với người cao tuổi phủ toàn bộ mạng lưới.

Dữ liệu ra

Mỗi dòng mô tả một hành trình bằng dãy số hiệu các giao lộ theo thứ tự người đưa thư đi qua. Giao lộ xuất phát, cũng là giao lộ kết thúc, được in đầu tiên và chỉ in đúng một lần. Sau giao lộ cuối cùng được in, người đưa thư quay về giao lộ đầu tiên.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(3 \le N \le 500\,000\).
• \(3 \le M \le 500\,000\).
• Mạng lưới thỏa mãn tất cả điều kiện đã nêu trong phần dữ liệu vào.

Phân nhóm

1. 38 điểm: \(3 \le N \le 2000\), \(3 \le M \le 100\,000\).
2. 17 điểm: \(3 \le N \le 100\,000\), \(3 \le M \le 100\,000\).
3. 45 điểm: \(3 \le N \le 500\,000\), \(3 \le M \le 500\,000\).

Ví dụ

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

2 3 4 5 8 10 9
7 8 4
1 5 7 6 3