Giao Các Nửa Mặt Phẳng

Buổi 61 — Hình học tính toán
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho $N$ nửa mặt phẳng trên hệ tọa độ $Oxy$. Mỗi nửa mặt phẳng được xác định bởi một đường thẳng có hướng đi từ $A(x_1, y_1)$ đến $B(x_2, y_2)$ ($A \ne B$) và lấy phần mặt phẳng nằm ở bên trái (hoặc trên) tia $\vec{AB}$.

Biết vùng giao nằm gọn trong hình vuông $[-10^6, 10^6] \times [-10^6, 10^6]$ (hoặc rỗng). Hãy tính diện tích phần giao của tất cả $N$ nửa mặt phẳng này.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^4$).
  • $N$ dòng tiếp theo, mỗi dòng chứa $4$ số nguyên $x_1, y_1, x_2, y_2$ ($|x|, |y| \le 10^5$).
Dữ liệu ra
  • In ra một số thực là diện tích phần giao của $N$ nửa mặt phẳng, làm tròn đến $6$ chữ số thập phân (in 0.000000 nếu giao rỗng).
Ví dụ
Input Output
4
0 0 4 0
4 0 4 4
4 4 0 4
0 4 0 0
16.000000
Giới hạn
  • $1 \le N \le 10^4$
  • $|x|, |y| \le 10^5$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved