Trồng rau

Xem PDF

Nộp bài


Điểm: 20 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M

Tác giả:
Dạng bài

Sau đợt tập huấn dài chuẩn bị cho kì thi VOI, Bảo Anh quyết định sẽ đi phượt để giải tỏa stress. Hôm nay, Anh sẽ đến Tam Kì để thăm người đàn anh thân thiết của mình. Vừa hay, đàn anh của Anh đang bận trồng rau làm ruộng cho vụ mùa năm nay. Vì không muốn tới chơi nhưng không được tiếp đón, Bảo Anh quyết định sẽ giúp người đàn anh hoàn thành công việc sớm.

Thửa ruộng của người đàn anh có 2 loại rau, rau ăn đượcrau trồng cho vui. Người đàn anh đang muốn xây một hàng rào hình chữ nhật với các cạnh song song với các trục tọa độ, sao cho trong hình chữ nhật chỉ chứa loại rau ăn được (một bó rau được tính là bao bọc ngay cả khi nó nằm trên ranh giới hàng rào). Trong số tất cả hàng rào có thể xây được, người đàn anh muốn xây hàng rào bao được nhiều loại rau ăn được nhất. Và trong số các hàng rào này, người đàn anh muốn xây hàng rào có diện tích nhỏ nhất có thể. Hàng rào với chiều dài hoặc chiều rộng bằng 0 vẫn được phép.

Bảo Anh muốn giúp người đàn anh hoàn thành công việc, nhưng cậu cũng không muốn làm việc khi đang đi phượt. Vì vậy, bạn hãy giúp Bảo Anh giải bài toán này nhé.

INPUT

  • Dòng đầu tiên gồm số nguyên dương \(N\) (\(1 \leq N \leq 500\))
  • \(N\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(x, y\) (\(0 \leq x, y \leq 1000\)) và 1 kí tự, mô tả tọa độ và loại của rau \(i\). Kí tự H mô tả rau ăn được và G là rau trồng cho vui. Không có 2 bó rau nào ở cùng 1 tọa độ, và có ít nhất 1 bó rau là rau ăn được

OUTPUT

Gồm 2 dòng. Dòng 1 chứa số lượng rau ăn được lớn nhất trong hàng rào mà không có bó rau trồng cho vui nào. Dòng 2 chứa số nguyên là diện tích nhỏ nhất có thể của hàng rào đó.

VÍ DỤ:

INPUT:

5
1 1 H
4 4 H
6 6 H
3 3 G
2 2 H

OUTPUT:

2
1

Nguồn bài: Lê Phước Định và Lê Phước Anh Kha.