RECLAND - Rectangle Land
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 10.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: psucoder

Hành tinh Shape có một quốc gia xinh đẹp và giàu có tên là Rectangle Land. Cạnh đó là một quốc gia khác tên gọi Circle Land. Vào một đêm không trăng không sao, Rectangle Land bị nước láng giềng là Circle Land bất ngờ dội bom. Do không đề phòng nên quốc vương Rectangle Land chỉ biết quan ngại sâu sắc và cực lực lên án hành vi tàn bạo, phi nhân tính của người anh em Circle. Đồng thời ông cũng cho người thống kê thiệt hại để báo cáo lên Liên hiệp Shape.

Những quả bom của Circle vốn dĩ có hình cầu, nhưng khi rơi xuống Rectangle Land thì lại gây thiệt hại lên một vùng có hình chữ nhật. Bom có sức công phá càng lớn thì thiệt hại càng lớn. Nếu một khu vực bị ảnh hưởng của nhiều quả bom thì sẽ chịu thiệt hại sẽ là tổng thiệt hại của các quả bom đó gây ra.

Vì bản thống kê thiệt hại quá dài nên quốc vương Rectangle Land chỉ yêu cầu tính cho ông vùng đất nào bị thiệt hại nặng nề nhất, và diện tích vùng đất đó là bao nhiêu. Bạn hãy giúp quốc vương nhé!

 

Input:

- Dòng đầu tiên là n (1 <= n <= 100.000) tương ứng với số quả bom.

- n dòng tiếp theo, mỗi dòng chứa 5 số x1, y1, x2, y2, s theo thứ tự là vùng ảnh hưởng và sức công phá của mỗi quả bom (-106 <= x1 < x2 <= 106, -106 <= y1 < y2 <= 106, 1 <= s <= 104). Trong đó (x1, y1) là toạ độ góc trái dưới, (x2, y2) là toạ độ góc phải trên, s là sức công phá tương đương với thiệt hại do quả bom đó gây ra.

Output:

Một dòng duy nhất chứa 2 số nguyên: số thứ nhất là giá trị thiệt hại của vùng bị thiệt hại nặng nhất, số thứ hai là diện tích của vùng đó.

Ví dụ

  • input
    3
    0 3 4 6 1
    1 4 6 8 2
    2 0 8 5 3
    output
    6 2
  • input
    1
    0 0 1000 1000 7
    output
    7 1000000

Giải thích ví dụ:

Ở test 1, vùng có thiệt hại nặng nề nhất có toạ độ góc trái dưới là (2, 4), toạ độ góc phải trên là (4, 5), giá trị thiệt hại là 6, diện tích là 2.

Nguồn: open.kattis.com

Back to Top