Ghép cặp hộp quà

Buổi 73-74 — Virtual CF greedy sorting
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $n$ chiếc hộp có kích thước $a_1, a_2, \dots, a_n$. Một chiếc hộp kích thước $x$ có thể được lồng vào bên trong một chiếc hộp kích thước $y$ nếu $y \ge 2x$. Mỗi chiếc hộp lớn chỉ chứa được tối đa $1$ chiếc hộp nhỏ bên trong (và chiếc hộp nhỏ đó không thể chứa thêm hộp nào khác). Hãy tìm số chiếc hộp tối thiểu nhìn thấy được sau khi lồng ghép tối ưu.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $n$ ($1 \le n \le 5 \cdot 10^5$).
  • Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$).
Dữ liệu ra
  • 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
    • Một số nguyên duy nhất là số hộp tối thiểu còn lại bên ngoài.
    Ví dụ
    Input Output
    8
    2 5 7 6 9 8 4 2
    5
    Giới hạn
    • $1 \le n \le 5 \cdot 10^5$
    Draft saved