Đăng ký
cpp-062Đọc toàn bộ đề miễn phí

Kiểm tra điểm trong đa giác: Thuật toán Bắn tia Ray Casting

Cho một đa giác gồm N đỉnh V1, V2, …, VN theo thứ tự duyệt viền. Bạn cần trả lời M truy vấn, mỗi truy vấn cho một điểm P(X, Y) và yêu cầu xác định P nằm INSIDE, BOUNDARY hay…

C++Nâng cao45 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

geometryray castingpoint in polygonintersection

Kiến thức tiên quyết: geometry primitives, line segment intersection.

Nội dung đề bài

Mục tiêu kiến thức

  • Nắm vững thuật toán bắn tia (Ray Casting Algorithm) kiểm tra vị trí tương đối của điểm so với đa giác bất kỳ (có thể không lồi).
  • Phân biệt 3 trạng thái: INSIDE (bên trong), BOUNDARY (nằm trên cạnh), OUTSIDE (bên ngoài).
  • Xử lý triệt để các trường hợp biên: tia đi qua đỉnh đa giác, tia trùng cạnh đa giác.

Mô tả bài toán

Cho một đa giác gồm N đỉnh V1, V2, …, VN theo thứ tự duyệt viền. Bạn cần trả lời M truy vấn, mỗi truy vấn cho một điểm P(X, Y) và yêu cầu xác định P nằm INSIDE, BOUNDARY hay OUTSIDE đa giác.

Quy ước nộp bài

  • Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
  • Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
  • Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
  • Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

  • Dòng 1: Gồm 2 số nguyên N, M (3 ≤ N ≤ 1000, 1 ≤ M ≤ 1000).
  • N dòng tiếp theo: Mỗi dòng gồm 2 số nguyên mô tả tọa độ đỉnh của đa giác.
  • M dòng tiếp theo: Mỗi dòng gồm 2 số nguyên mô tả tọa độ điểm cần kiểm tra.

Output

  • Với mỗi truy vấn, in ra kết quả trên một dòng: INSIDE, BOUNDARY hoặc OUTSIDE.

Ràng buộc

  • Tọa độ các điểm nằm trong đoạn [-109, 109].
  • Thời gian: 1000ms. Bộ nhớ: 256MB.

Ví dụ 1

Input

4 3
0 0
10 0
10 10
0 10
5 5
0 5
15 15

Output

INSIDE
BOUNDARY
OUTSIDE
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Bài tập liên quan cùng chuyên đề

Bao lồi tập điểm: Thuật toán Chuỗi đơn điệu Andrew Monotone Chain
Nâng cao45p
Cặp điểm gần nhất: Thuật toán Chia để trị O(N log N)
Nâng cao50p
Diện tích đa giác và Định lý Pick trên lưới nguyên
Nâng cao40p
Giao các nửa mặt phẳng trong O(N log N)
Nâng cao55p

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.