Vùng An Toàn Radar
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Hệ thống phòng thủ gồm $N$ trạm radar đặt tại các tọa độ nguyên $(x_i, y_i)$ trên mặt phẳng $Oxy$. Vùng an toàn được xác định là bao lồi (convex hull) của $N$ trạm radar này (bao gồm cả phần bên trong và trên biên).
Có $Q$ mục tiêu xuất hiện tại các tọa độ $(u_j, v_j)$. Hãy tính:
- Hai lần diện tích của vùng an toàn ($2 \times S$).
- Số lượng mục tiêu nằm bên trong hoặc trên biên của vùng an toàn.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($3 \le N \le 10^5$, $1 \le Q \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($|x_i|, |y_i| \le 10^8$) là tọa độ trạm radar thứ $i$. Đảm bảo không phải tất cả $N$ điểm đều thẳng hàng.
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_j, v_j$ ($|u_j|, |v_j| \le 10^8$) là tọa độ mục tiêu thứ $j$.
Kết quả
- Dòng đầu tiên in ra một số nguyên là $2 \times S$.
- Dòng thứ hai in ra một số nguyên là số lượng mục tiêu nằm trong hoặc trên biên của vùng an toàn.
Subtasks
- Subtask 1 (20%): $N, Q \le 100$.
- Subtask 2 (30%): $N, Q \le 2000$.
- Subtask 3 (50%): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 4 3 0 0 4 0 4 4 0 4 2 2 4 2 5 5 |
32 2 |
Community Discussion