Giao các nửa mặt phẳng trong O(N log N)

Mô tả bài toán

Một nửa mặt phẳng có hướng được biểu diễn bởi tia đi từ điểm P đến điểm Q, quy ước nửa mặt phẳng hợp lệ nằm ở phía bên trái của vector PQ (tức là PQ × PX ≥ 0).

Cho N nửa mặt phẳng và một hộp giới hạn [-10⁴, 10⁴] × [-10⁴, 10⁴].

Yêu cầu: Tính diện tích phần giao chung (miền khả thi lồi) của tất cả N nửa mặt phẳng này bên trong hộp giới hạn. Kết quả in ra với đúng 2 chữ số thập phân.

Dữ liệu vào

• Dòng đầu chứa số nguyên N (1 ≤ N ≤ 50,000).
• N dòng tiếp theo, mỗi dòng gồm 4 số nguyên x₁, y₁, x₂, y₂ đại diện cho vector có hướng từ (x₁, y₁) đến (x₂, y₂) xác định nửa mặt phẳng bên trái (-10⁴ ≤ x_i, y_i ≤ 10⁴, hai điểm phân biệt).

Dữ liệu ra

• In ra một số thực duy nhất là diện tích phần giao với 2 chữ số thập phân sau dấu phẩy (ví dụ: 100.00).

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ả.