IOI 2004 - Ngày 1

Zeus giao cho Artemis, nữ thần của thiên nhiên hoang dã, một khu đất hình chữ nhật để trồng rừng. Góc dưới bên trái của khu đất là \((0,0)\); cạnh trái nằm trên trục tung không âm và cạnh dưới nằm trên trục hoành không âm. Các cây chỉ được trồng tại những điểm có tọa độ nguyên. Để khu rừng trông tự nhiên, Artemis trồng sao cho không có hai cây nào cùng hoành độ hoặc cùng tung độ.

Khi Zeus cần gỗ, Artemis phải chọn một vùng để chặt cây thỏa mãn các điều kiện sau:

1. Có ít nhất \(T\) cây bị chặt.
2. Vùng được chọn là hình chữ nhật; mọi cây trong vùng đều bị chặt và không cây nào ngoài vùng bị chặt. Khu đất trống sẽ được dùng làm sân bóng đá.
3. Các cạnh hình chữ nhật song song với hai trục tọa độ.
4. Hai góc đối diện của hình chữ nhật nằm tại hai cây. Hai cây ở góc này cũng bị chặt.

Artemis muốn giữ lại càng nhiều cây càng tốt. Hãy tìm một vùng thỏa mãn các điều kiện trên và có số cây bị chặt nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), số cây trong rừng.
• Dòng thứ hai chứa số nguyên \(T\), số cây ít nhất phải chặt.
• \(N\) dòng tiếp theo mô tả các cây theo thứ tự đánh số từ \(1\) đến \(N\). Mỗi dòng chứa hai số nguyên \(X,Y\), lần lượt là hoành độ và tung độ của một cây.

Dữ liệu ra

In hai số nguyên \(I,J\) trên một dòng, cách nhau bởi một dấu cách. Cây thứ \(I\) và cây thứ \(J\) là hai góc đối diện của vùng được chọn. Tọa độ của chúng nằm ở dòng \(I+2\) và \(J+2\) của dữ liệu vào.

Thứ tự của \(I,J\) không quan trọng. Nếu có nhiều cách chọn tối ưu, có thể in bất kỳ cách nào. Mọi bộ kiểm thử đều có ít nhất một lời giải.

Ràng buộc

• \(1<N\le20000\).
• \(0\le X,Y\le64000\).
• \(1<T\le N\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(1<N<5000\).

Ví dụ

3
2
1 1
2 3
5 6

1 2

Thành phố của các vị thần Hy Lạp có mạng đường dạng lưới. Với mỗi số nguyên \(Z\), có một đường ngang \(y=Z\) và một đường dọc \(x=Z\). Các giao lộ vì thế có tọa độ nguyên. Trong những ngày nóng bức, các vị thần nghỉ ở những quán cà phê tại các giao lộ.

Thần đưa tin Hermes phải di chuyển dọc theo các con đường để gửi một dãy thông điệp ánh sáng. Mỗi thông điệp dành cho một vị thần; việc các vị thần khác nhìn thấy thông điệp không ảnh hưởng gì.

Hermes xuất phát tại \((0,0)\) và phải gửi các thông điệp theo đúng thứ tự đã cho. Để gửi thông điệp đến quán ở \((X_i,Y_i)\), Hermes chỉ cần đến một điểm bất kỳ trên đường ngang \(y=Y_i\) hoặc trên đường dọc \(x=X_i\). Sau khi gửi hết các thông điệp, Hermes dừng lại.

Hãy tìm tổng quãng đường nhỏ nhất Hermes phải đi.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\), số thông điệp cần gửi.
• \(N\) dòng tiếp theo mô tả các quán theo thứ tự gửi thông điệp. Mỗi dòng chứa hai số nguyên: hoành độ rồi đến tung độ của quán.

Dữ liệu ra

In một số nguyên trên một dòng: tổng quãng đường nhỏ nhất Hermes phải đi để gửi hết các thông điệp.

Ràng buộc

• \(1\le N\le 20000\).
• \(-1000\le X_i,Y_i\le 1000\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(N\le 80\).

Ví dụ

5
8 3
7 -7
8 1
-2 1
6 -5

11

Một đa giác gồm tất cả các điểm nằm trên biên hoặc trong miền được biên bao quanh. Đa giác lồi có tính chất: với hai điểm bất kỳ thuộc đa giác, đoạn thẳng nối chúng cũng nằm trong đa giác.

Trong bài này, mọi đa giác đều lồi, có ít nhất hai đỉnh, các đỉnh đôi một khác nhau và có tọa độ nguyên; không có ba đỉnh nào thẳng hàng. Một đoạn thẳng được coi là đa giác có hai đỉnh.

Tổng Minkowski của hai đa giác \(A,B\) là tập hợp tất cả các điểm \((x_1+x_2,y_1+y_2)\), với \((x_1,y_1)\) thuộc \(A\) và \((x_2,y_2)\) thuộc \(B\). Tổng Minkowski của hai đa giác cũng là một đa giác. Hình dưới minh họa hai tam giác và tổng Minkowski của chúng.

Cho đa giác \(P\), hãy tìm hai đa giác \(A,B\) sao cho:

• \(P\) là tổng Minkowski của \(A\) và \(B\).
• \(A\) có từ 2 đến 4 đỉnh, tức là một đoạn thẳng, tam giác hoặc tứ giác.
• Số đỉnh của \(A\) lớn nhất có thể: ưu tiên tứ giác; nếu không thể thì chọn tam giác; nếu cả hai đều không thể thì chọn đoạn thẳng.

Cả \(A\) lẫn \(B\) đều không thể bằng \(P\), vì khi đó đa giác còn lại phải là một điểm, mà một điểm không phải là đa giác hợp lệ trong bài này.

Đây là bài chỉ nộp kết quả. Với mỗi tệp dữ liệu vào được cung cấp, hãy tạo tệp kết quả mô tả \(A\) và \(B\). Không nộp chương trình. Mỗi dữ liệu vào đều có ít nhất một cách phân tích hợp lệ; nếu có nhiều kết quả tối ưu, có thể chọn bất kỳ kết quả nào.

Dữ liệu vào

Có 10 tệp polygon1.in đến polygon10.in. Số trong tên tệp là số thứ tự của bộ dữ liệu.

• Dòng đầu chứa số nguyên \(N\), số đỉnh của \(P\).
• \(N\) dòng tiếp theo liệt kê các đỉnh theo chiều ngược kim đồng hồ. Dòng \(i+1\) chứa hai số nguyên \(X_i,Y_i\), là tọa độ đỉnh thứ \(i\), cách nhau bởi một dấu cách.
• Mọi tọa độ trong dữ liệu vào đều là số nguyên không âm.

Dữ liệu ra

Nộp 10 tệp kết quả tương ứng với 10 tệp dữ liệu vào. Tệp kết quả cho bộ dữ liệu số \(I\) phải có dòng đầu là #FILE polygon I, trong đó \(1\le I\le10\).

• Dòng thứ hai chứa số nguyên \(N_A\), số đỉnh của \(A\), với \(2\le N_A\le4\).
• \(N_A\) dòng tiếp theo chứa tọa độ các đỉnh của \(A\) theo chiều ngược kim đồng hồ, mỗi dòng hai số nguyên \(X,Y\) cách nhau bởi một dấu cách. Đỉnh thứ \(i\) nằm ở dòng \(i+2\).
• Dòng \(N_A+3\) chứa số nguyên \(N_B\), số đỉnh của \(B\), với \(N_B\ge2\).
• \(N_B\) dòng tiếp theo chứa tọa độ các đỉnh của \(B\) theo chiều ngược kim đồng hồ, mỗi dòng hai số nguyên \(X,Y\) cách nhau bởi một dấu cách. Đỉnh thứ \(j\) nằm ở dòng \(N_A+j+3\).

Trong phiên bản trên LQDOJ, mọi tọa độ trong dữ liệu ra phải thỏa mãn \(-10^{18}\le X,Y\le10^{18}\). Đây là giới hạn bổ sung so với đề gốc. Với mỗi bộ dữ liệu được cung cấp, tồn tại kết quả tối ưu thỏa mãn giới hạn này.

Phân nhóm

Có 10 bộ dữ liệu, mỗi bộ có số điểm tối đa là 10.

Ví dụ

5
0 1
0 0
2 0
2 1
1 2

#FILE polygon 0
3
0 0
2 0
1 1
2
0 1
0 0

#FILE polygon 0
3
0 0
1 0
1 1
3
0 1
0 0
1 0