[THHV 2016 - CHL - 11] Bài 3: Lễ hội
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
Carnaval Hạ Long là một trong những lễ hội đường phố sống động vào đêm ngày 30 tháng 4 hàng năm của thành phố Hạ Long. Năm nay du khách dự lễ hội được thả đèn trời. Thắng được bố mẹ cho đi dự lễ hội và cậu bé rất thích thú với đèn trời. Đèn trời gồm hai loại lớn và nhỏ. Hình ảnh gây ấn tượng với Thắng là có một đèn trời nhỏ nằm trong hoặc trên cạnh của một tam giác có 3 đỉnh là 3 đèn trời lớn. Trong bài toán này ta coi bầu trời như mặt phẳng tọa độ và mỗi đèn trời như một điểm trên mặt phẳng đó.
Yêu cầu: Cho trước tọa độ của các đèn trời lớn và đèn trời nhỏ, hãy giúp Thắng đếm xem có bao nhiêu đèn trời nhỏ nằm trong hoặc trên cạnh của một tam giác nào đó có 3 đỉnh là 3 đèn trời lớn.
Input
- Dòng đầu tiên chứa số nguyên ~n~ (~3 \le n \le 10.000~) là số đèn trời lớn.
- Mỗi dòng trong ~n~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ (~0 \le x_i, y_i \le 2^{30}~) là tọa độ của một đèn trời lớn.
- Dòng tiếp theo ghi số nguyên ~k~ (~1 \le k \le 50.000~) là số đèn trời nhỏ.
- Mỗi dòng trong ~k~ dòng tiếp theo chứa hai số nguyên ~x_j, y_j~ (~0 \le x_j, y_j \le 2^{30}~) là tọa độ của một đèn trời nhỏ. Các điểm biểu thị đèn trời lớn và nhỏ là phân biệt và có ít nhất 3 điểm biểu thị đèn trời lớn là không thẳng hàng.
Output
- Ghi ra số đèn trời nhỏ nằm trong hoặc trên cạnh của một tam giác nào đó có 3 đỉnh là 3 đèn trời lớn.
Sample Input 1
8
3 4
2 8
5 4
1 8
4 7
3 10
11 2
7 3
6
5 12
3 7
3 3
4 5
0 4
2 6
Sample Output 1
3
Bình luận