123Code...

Nội dung Bài tập

Mã:: OLP17.CT3.CMP

Tên:: CMP

Dạng thi:: oi

Thang điểm:: 100 điểm

Giới hạn thời gian:: 1 giây

Giới hạn bộ nhớ:: 256 MB

Nguồn bài tập:: Olympic tin học 2017

Được tạo bởi:: admin

: Share

Input	Output
3 3 3 6 9 4 7 8 5 5 14 -1 13 4 9 4 6 2 8 -2 3 11 0 11 2 9 2 5 3 6 7 8 1	NO YES YES

Trong mặt phẳng, một đường gấp khúc khép kín được gọi là đa giác. Toàn bộ đa giác nằm cùng một phía của đường thẳng chứa cạnh bất kì của đa giác thì được gọi là đa giác lồi. Đa đa giác lồi (CMP) là tập hợp nhiều đa giác lồi không cắt nhau, mỗi đa giác lồi được gọi là 1 đường biên của CMP. Hai đường biên có thể là lồng nhau hoặc rời nhau. Tổ chức các đường biên theo mối quan hệ lồng nhau từ ngoài vào trong, khi đó, các đường biên ở lớp ngoài cùng được gọi là đường biên ngoài, lớp kế tiếp là đường biên trong, kế tiếp lại là biên ngoài, ... Một CMP cần có ít nhất một đường biên ngoài và có thể không có đường biên trong nào cả. Phần mặt phẳng nằm giữa đường biên ngoài và đường biên trong (kể cả trên cạnh) được gọi là phần trong của CMP. Một điểm trên mặt phẳng được gọi là nằm trong CMP nếu nó thuộc vào phần trong của CMP, ngược lại là nằm ngoài. Ví dụ, hình trên là đa đa giác lồi, phần màu xám là phần trong của đa đa giác lồi. Bài toán: cho đa đa giác lồi CMP, xác định điểm P(x, y) nằm trong hay ngoài CMP. Dữ liệu: Vào từ thiết bị vào chuẩn có cấu trúc như sau: Dòng thứ nhất ghi 2 số nguyên dương N và Q (0 < N ≤ 3000, 0 < Q ≤ 10⁵): N – số đường biên của CMP; Q – số truy vấn cần xác định điểm nằm trong hay ngoài CMP. N dòng tiếp theo mỗi dòng ghi số nguyên M (2 < M ≤ 300) xác định số đỉnh của đường biên và sau đó là M cặp số (x, y) cho biết tọa độ các đỉnh trên đường biên này. Các đỉnh được ghi nhận theo trình tự ngược chiều kim đồng hồ (|x|, |y| ≤ 10⁶). Q dòng tiếp theo, mỗi dòng ghi 2 số x_p, y_p cho biết truy vấn điểm có tọa độ (x_p, y_p) có nằm trong CMP hay không (|x_p|, |y_p| ≤ 10⁶). Kết quả: Đưa ra thiết bị ra chuẩn gồm Q dòng, mỗi dòng ghi câu trả lời (YES/NO) tương ứng với Q truy vấn trong dữ liệu vào. Ví dụ: Input Output 3 3 3 6 9 4 7 8 5 5 14 -1 13 4 9 4 6 2 8 -2 3 11 0 11 2 9 2 5 3 6 7 8 1 NO YES YES
Quảng cáo