Tổng Minkowski của hai đa giác lồi trong O(N + M)

Mô tả bài toán

Cho hai đa giác lồi P (gồm N đỉnh) và Q (gồm M đỉnh) trên mặt phẳng Oxy. Các đỉnh của mỗi đa giác được liệt kê theo chiều ngược chiều kim đồng hồ (CCW).

Tổng Minkowski của P và Q, ký hiệu P oplus Q, là tập hợp tất cả các điểm có dạng: P oplus Q = {p + q | p ∈ P, q ∈ Q} Đa giác kết quả cũng là một đa giác lồi có không quá N + M đỉnh.

Yêu cầu: Hãy tính diện tích của đa giác tổng Minkowski P oplus Q. Kết quả in ra với đúng 1 chữ số thập phân sau dấu phẩy.

Dữ liệu vào

• Dòng đầu chứa số nguyên N (3 ≤ N ≤ 100,000).
• N dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y là tọa độ một đỉnh của P theo thứ tự CCW (-10⁶ ≤ x, y ≤ 10⁶).
• Dòng tiếp theo chứa số nguyên M (3 ≤ M ≤ 100,000).
• M dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y là tọa độ một đỉnh của Q theo thứ tự CCW (-10⁶ ≤ x, y ≤ 10⁶).

Dữ liệu ra

• In ra một số thực duy nhất là diện tích của đa giác P oplus Q, định dạng đúng 1 chữ số thập phân sau dấu phẩy (ví dụ: 18.0).

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.