Nội dung Bài tập
Mã:
OLP17.CT2.COVERAGE
Tên:
Phủ sống
Dạ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
Được tạo bởi:
admin
Đặc khu kinh tế có hình chữ nhật kích thước m×n lô (m hàng, n cột), mỗi lô là một hình vuông đơn vị. Một công ty thuê k lô, lô thứ i ở vị trí (ui, vi) (1 ≤ ui ≤ m, 1 ≤ vi ≤ n, i = 1 ÷ k). Để thuận tiện liên lạc nội bộ và điều khiển ô tô không người lái người ta tổ chức phủ sóng wifi lên một số lô. Vùng được phủ sóng thỏa mãn các điều kiện:

  • Số lượng lô được phủ sóng là ít nhất,
  • Tất cả các lô đã thuê đều được phủ sóng,
  • Nếu trên một hàng (hoặc cột) có 2 lô được phủ sóng thì các lô cùng hàng (hoặc cột) giữa 2 lô đó cũng được phủ sóng,
  • Giữa 2 lô bất kỳ được phủ sóng phải có đường đi chỉ theo các lô đã phủ sóng. Từ một lô chỉ có thể đi sang lô khác kề cạnh.
Có thể có nhiều sơ đồ khác nhau phủ sóng thỏa mãn các điều kiện đã nêu và một trong các sơ đồ đã được hiện thực hóa.

Sự phát triển của Công ty đòi hỏi cần thuê thêm một lô. Có q phương án lựa chọn, phương án thứ j là thuê lô (xj, yj) (1 ≤ xj ≤ m, 1 ≤ yj ≤ n, j = 1 ÷ q).

Với mỗi phương án thuê thêm hãy xác định chắc chắn ô này đã được phủ sóng hoặc chắc chắn ngoài vùng phủ sóng hay có thể có hoặc không có sóng tùy thuộc vào sơ đồ phủ sóng đang hoạt động và đưa ra thông báo tương ứng là Yes hoặc No hay May be.

Dữ liệu: Vào từ thiết bị vào chuẩn:
  • Dòng đầu tiên chứa 3 số nguyên m, n và k (1 ≤ m, n ≤ 10 000, 1 ≤ k ≤ 105),
  • Dòng thứ i trong k dòng sau chứa 2 số nguyên ui và vi (1 ≤ ui ≤ m, 1 ≤ vi ≤ n), không có 2 dòng giống nhau.
  • Dòng tiếp theo chứa số nguyên q (1 ≤ q ≤ 104),
  • Dòng thứ j trong q dòng sau chứa 2 số nguyên xj và yj (1 ≤ xj ≤ m, 1 ≤ yj ≤ n), các dòng khác nhau từng đôi một.
Các số trên một dòng ghi cách nhau một dấu cách (dấu trắng).

Kết quả: Đưa ra thiết bị ra chuẩn q dòng các thông báo xác định được, thông báo thứ j tương ứng với phương án j ( j = 1 ÷ q).

Ví dụ:

InputOutput
5 5 8 
1 1 
2 2 
3 4 
3 2 
5 4 
4 4 
4 5 
4 3 
3 
2 1 
3 3 
5 5
May be 
Yes 
No



    Quảng cáo
       Ngôn ngữ : 

       Theme : 
Mời bạn soạn code



		



      Ai có thể xem bài này : 

Thông tin



Phần thảo luận