Chọn ĐTQG Đồng Tháp 2025 - Cứu hộ
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Thành phố của Alice lên kế hoạch xây dựng một trạm cứu hộ để có thể phản ứng nhanh với các tình huống khẩn cấp. Vị trí dự kiến của trạm cứu hộ có tọa độ ~(x_0, y_0)~.
Có ~n~ khu vực dân cư, khu vực thứ ~i~ (~1 \le i \le n~) có tâm ở tọa độ ~(x_i, y_i)~. Để đánh giá mức độ hiệu quả và khả năng bao quát của vị trí trạm cứu hộ, Alice đưa ra khái niệm "tam giác hỗ trợ". Một tam giác hỗ trợ được định nghĩa là khu vực nằm trong tam giác có ba đỉnh là tâm của ba khu vực dân cư. Một vị trí được coi là lý tưởng nếu nó nằm hoàn toàn bên trong (không tính nằm trên cạnh) nhiều tam giác hỗ trợ nhất, điều này cho thấy khả năng tiếp cận và phục vụ đến các khu vực dân cư.
Yêu cầu: Cho thông tin ~(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)~, hãy giúp Alice đếm số lượng tam giác hỗ trợ chứa hoàn toàn vị trí của trạm cứu hộ.
Input
- Dòng đầu chứa số nguyên dương ~n~ (~n \le 10^5~).
- Dòng thứ hai chứa hai số nguyên là tọa độ vị trí dự kiến của trạm cứu hộ ~(|x_0|, |y_0| \le 10^9)~.
- Tiếp theo là ~n~ dòng, mỗi dòng chứa hai số nguyên là tọa độ tâm của từng khu vực dân cư ~(|x_i|, |y_i| \le 10^9; 1 \le i \le n)~. Dữ liệu bảo đảm tọa độ vị trí trạm cứu hộ và tọa độ tâm của các khu vực dân cư không trùng nhau.
Output
- Ghi ra một dòng chứa một số là số lượng tam giác hỗ trợ chứa vị trí của trạm cứu hộ.
Subtasks
- Có ~10%~ số test của bài có ~n = 3~.
- Có ~30%~ số test khác của bài có tính chất: ~n \le 100~.
- Có ~30%~ số test khác của bài có tính chất: ~n \le 2000~.
- Có ~30%~ số test còn lại của bài không có ràng buộc nào thêm.
Sample Input 1
3
0 0
0 1
-1 0
1 -1
Sample Output 1
1
Sample Input 2
4
0 0
0 1
-1 0
1 0
-1 -1
Sample Output 2
1
Bình luận