(COVERING.*)

Mệt mỏi vì có quá nhiều bài tập về nhà, Bắc tiện tay lấy tập giấy màu thủ công của em Ninh và cắt thành \(n\) hình chữ nhật có cạnh là các số chẵn. Các hình chữ nhật sau đó được dán chồng lên nhau sao cho các cạnh của chúng song song với các trục tọa độ và tâm của tất cả \(\mathbf{n}\) hình chữ nhật trùng nhau.

Kết quả là Bắc có một hình đa giác đầy màu sắc. Vốn là một học sinh chuyên Toán, Bắc muốn thư giãn bằng cách tìm diện tích hình đa giác kì lạ của mình.

Yêu cầu: Cho \(n\) hình chữ nhật có độ lớn các cạnh tương ứng là \(w\) và \(h\) (\(w\) và \(h\) chẵn). Tìm diện tích phủ bởi \(n\) hình chữ nhật khi xếp chúng như mô tả.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\left( 1 \leq n \leq 10^{5} \right)\).

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa 2 số nguyên chẵn \(w_{i},h_{i}\left( 2 \leq w_{i},h_{i} \leq 10^{9} \right)\) – tương ứng chiều rộng và chiều cao của hình chữ nhật thứ \(i\).

Kết quả: Một số nguyên là kết quả bài toán.

Ví dụ:

Ràng buộc: 50% số test có \(\mathbf{n},\ \mathbf{w}_{\mathbf{i}},\ \mathbf{c}_{\mathbf{i}} \leq \mathbf{100}\)

Solution

Giả sử tâm của tất cả các hình chữ nhật là \((0,0)\). Khi đã có tọa độ tâm và kích thước 2 cạnh liên tiếp của hình chữ nhật ta có thể tìm ra tọa độ các đỉnh của hình chữ nhật đó.

Sub1:

Với mỗi hình chữ nhật, ta đánh dấu tất cả các ô trong nó. Cuối cùng chỉ cần đếm tất cả các ô được đánh dấu.

Sub 2:

Sắp xếp các hình chữ nhật theo thứ tự tăng dần của tọa độ trái. Sau khi sắp xếp ta dễ tính được phần diện tích không giao nhau của hai hình chữ nhật liên tiếp nhau.