Vùng An Toàn Radar

Binary-search Buổi 67-68 — Mock IOI
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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:

  1. Hai lần diện tích của vùng an toàn ($2 \times S$).
  2. 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
Draft saved