BOI 2009 - Ngày 2

Cho \(n\) điểm trên mặt phẳng tọa độ.

Hãy tính diện tích lớn nhất của một hình chữ nhật có cả bốn đỉnh thuộc tập điểm đã cho. Dữ liệu bảo đảm tồn tại ít nhất một hình chữ nhật như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), số điểm. Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số nguyên, là tọa độ của một điểm. Không có hai điểm trùng nhau.

Dữ liệu ra

In ra một số nguyên duy nhất: diện tích lớn nhất của một hình chữ nhật thỏa mãn.

Ràng buộc

Mỗi tọa độ nằm trong đoạn \([-10^8,10^8]\).

Phân nhóm

• 20% số điểm: \(n\le 500\).

Ví dụ

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

10

Một phép tam giác hóa đa giác là một tập các tam giác có đỉnh là các đỉnh của đa giác, không chồng lấn và phủ kín toàn bộ đa giác.

Ta gọi một đường cắt đa giác là một đường thẳng chia đa giác thành hai phần.

Cho một đa giác lồi đã được tam giác hóa, trong đó mỗi tam giác có một màu. Hãy tìm số đường cắt lớn nhất có thể thực hiện sao cho không có hai điểm cùng màu nằm trong hai phần khác nhau.

Dữ liệu vào

Dòng đầu chứa số đỉnh \(n\). Các đỉnh được đánh số bằng các số nguyên phân biệt từ \(1\) đến \(n\).

Mỗi dòng trong \(n-2\) dòng tiếp theo chứa bốn số nguyên \(a,b,c,d\), cho biết tam giác có ba đỉnh \(a,b,c\) mang màu \(d\). Ba đỉnh \(a,b,c\) đôi một khác nhau. Dữ liệu luôn mô tả một phép tam giác hóa hợp lệ và mọi tam giác đều đã được tô màu.

Dữ liệu ra

In ra một số nguyên duy nhất: số đường cắt lớn nhất.

Ràng buộc

Phân nhóm

• 50% số điểm: \(n\le 5\,000\).

Ví dụ

5
1 2 3 2
4 5 1 1
3 1 4 2

1

6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

0

Một triệu phú Thụy Điển muốn xây một đài tưởng niệm cho gia đình. Tên của mọi tổ tiên đã biết và các hậu duệ trong tương lai sẽ được khắc lên bốn mặt bên. Đài tưởng niệm là một khối hộp chữ nhật có đáy và mặt trên là hình vuông \(a\times a\), chiều cao \(b\); mỗi mặt bên có kích thước \(a\times b\). Cần chọn \(a,b\) để tổng diện tích bốn mặt bên, \(4ab\), lớn nhất.

Đài tưởng niệm được cắt từ một khối đá đặc biệt kích thước \(p\times q\times r\), kết tinh theo lưới lập phương đều. Có thể xem khối đá gồm các khối lập phương đơn vị \(1\times1\times1\), và đài tưởng niệm cuối cùng cũng phải gồm các khối như vậy. Chỉ được cắt vuông góc với các trục \(x,y,z\) và dọc theo ranh giới giữa các khối đơn vị.

Khối đá thô có các lỗ rỗng, tức những khối lập phương đơn vị bị khuyết. Đài tưởng niệm không được chứa bất kỳ lỗ rỗng nào. Cho bản đồ ba chiều của khối đá, hãy tìm \(a,b\) sao cho có thể cắt được đài tưởng niệm và \(4ab\) lớn nhất.

Dữ liệu vào

Dòng đầu chứa ba số nguyên dương \(p,q,r\). Tiếp theo là \(pq\) dòng, mỗi dòng gồm đúng \(r\) ký tự. Mỗi ký tự là N nếu khối đơn vị bình thường hoặc P nếu đó là lỗ rỗng.

Ký tự thứ \(z\) trên dòng thứ \((y-1)p+x\) mô tả khối đơn vị có tọa độ \((x,y,z)\), với \(1\le x\le p\), \(1\le y\le q\) và \(1\le z\le r\).

Dữ liệu ra

In ra giá trị lớn nhất của \(4ab\).

Ràng buộc

Ví dụ

3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP

24