VM 10 Bài 14 - KINGDOMS

View as PDF

Submit solution

Points: 1.90 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM10 - Tác giả : Nguyễn Hoành Tiến
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ở một vương quốc nọ, mỗi khi có một vị vua qua đời, hoàng tử cả sẽ lên ngôi và để thể hiện tình anh em, hoàng tử cả sẽ cắt một phần đất đai bên trong vương quốc cho các hoàng tử khác. Các hoàng tử này trờ thành vua chư hầu và xây dựng vương quốc của họ trên những phần đất được phân chia; và khi các hoàng tử này mất đi, các con của họ lại chia phần đất đó thành các vương quốc nhỏ hơn. Trải qua nhiều thế hệ, vương quốc to lớn ban đầu giờ đây đã trờ thành một tập hợp các vương quốc nhỏ; vương quốc này nằm trong vương quốc kia (Xem ví dụ để thấy rõ hơn). Điều này khiến cho việc quản lý các vương quốc hết sức phức tạp đến mức có những người dân cảm thấy bối rối vì không biết nhà mình thuộc về vương quốc nào. Bạn hãy lập một chương trình để giúp đỡ những người dân này.

Input

Dòng đầu gồm hai số ~N~ và ~Q~ thể hiện số lượng vương quốc và số lượng căn nhà.

~N~ dòng sau, dòng thứ ~i~ mô tả vương quốc thứ ~i~ có dạng: ~k~ ~x_1~ ~y_{1}~ ~x_{2}~ ~y_{2}~ ...~x_{k}~ ~y_{k}~. Dòng này thể hiện vương quốc ~i~ là một đa giác lồi ~k~ đỉnh; toạ độ các đỉnh theo chiều kim đồng hồ là (~x_1~, ~y_1~), (~x_{2}~, ~y_{2}~) ...(~x_{k}~, ~y_{k}~). Các đa giác không cắt nhau hay có điểm chung. Luôn tồn tại một đa giác chứa toàn bộ các đa giác còn lại.

~Q~ dòng cuối cùng; mỗi dòng gồm hai số ~x~ ~y~ là toạ độ một căn nhà. Không có căn nhà nào nằm trên biên giới giữa hai quốc gia.

Output

Gồm ~Q~ dòng, mỗi dòng ghi thứ tự của vương quốc mà căn nhà tương ứng thuộc về.

Giới hạn

  • ~Q < 22\,222~.
  • Tổng số lượng số đỉnh của các đa giác nhỏ hơn ~33\,333~. Trị tuyệt đối toạ độ các đỉnh và căn nhà nhỏ hơn ~999\,999\,999~.

Sample Input

5 3
4 0 1 1 7 6 8 7 0
3 2 4 5 6 6 1
4 3 7 4 6 3 5 2 6
5 1 3 2 3 3 2 3 1 1 2
4 4 4 5 4 5 3 4 3
5 7
2 2
5 5

Sample Output

1
4
2

Note

image

Hình vẽ trên thể hiện vị trí của ~5~ vương quốc. Vương quốc lớn nhất là vương quốc ~1~.

Bên trong vương quốc ~1~ có ba vương quốc nhỏ hơn có hình tam giác, tứ giác và ngũ giác lần lượt là vương quốc ~2~, ~3~ và ~4~.

Vương quốc cuối cùng là vương quốc ~5~ nằm trong lòng vương quốc ~2~.

Nếu một người dân sống ở toạ độ (~5~, ~7~) thì nhà anh ta thuộc về vương quốc ~1~.

Nếu sống ở toạ độ (~2~, ~2~) thì thuộc về vương quốc ~4~; ở (~5~, ~5~) thì thuộc về vương quốc ~2~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.