Hình Chữ Nhật Bò (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân có $N$ con bò, mỗi con ở vị trí $(x, y)$ trên mặt phẳng và thuộc một trong hai giống: Holstein (H) hoặc Guernsey (G). Cần xây dựng một hàng rào hình chữ nhật song song với các trục để bao quanh chỉ những con Holstein mà không chứa bất kỳ con Guernsey nào.

Tìm số lượng Holstein tối đa có thể bao quanh, rồi trong tất cả cách bao quanh được số lượng đó, tìm cách có diện tích hàng rào tối thiểu.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$ .

$N$ dòng tiếp theo, mỗi dòng chứa ba số: tọa độ $x$ , $y$ (hai số nguyên) và loại bò (ký tự H hoặc G).

Dữ liệu ra

Dòng đầu: số lượng Holstein tối đa. Dòng thứ hai: diện tích hàng rào tối thiểu cho số lượng đó.

Ràng buộc

$1 \leq N \leq 500$
$0 \leq x, y \leq 1000$
Tất cả vị trí đều khác nhau
Có ít nhất một con Holstein
Hàng rào có thể có chiều rộng hoặc chiều cao bằng 0

Ví dụ

Input	Output	Giải thích
5 1 1 H 2 2 H 3 3 G 4 4 H 6 6 H	2 1	Bao 2 con H ở (1,1) và (2,2), diện tích = $(2 - 1) \times (2 - 1) = 1$ .
5 886 630 G 175 634 G 782 675 H 567 938 G 862 132 H	2 43440	Bao 2 con H ở (782,675) và (862,132), diện tích = $\| 862 - 782 \| \times \| 675 - 132 \| = 80 \times 543 = 43440$ .

Bình luận

Không có bình luận tại thời điểm này.