NKLAND - Mảnh đất tổ tiên
Giới hạn- Thời gian: 0.61s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bờm sống trên mảnh đất tổ tiên để lại từ xa xưa. Tuy nhiên, trải qua bao đời, mảnh đất của Bờm ngày nay có thể đã bị thay đổi vị trí, thậm chí còn có thể không giao với mảnh đất của tổ tiên! Một ngày nọ, Bờm phát hiện tấm bản đồ mô tả hình dạng mảnh đất của tổ tiên. Bờm muốn xác định xem mảnh đất ngày nay và mảnh đất tổ tiên có còn giao nhau hay không!
Yêu cầu: Biết mảnh đất ngày nay của Bờm và mảnh đất của tổ tiên đều có hình dạng đa giác lồi. Hãy giúp Bờm xác định 2 mảnh đất có giao nhau (nghĩa là có phần diện tích chung) hay không.
Dữ liệu
Dòng đầu tiên chứa số nguyên t, cho biết số lượng test (t ≤ 10). t nhóm dòng tiếp theo mô tả các test, mỗi test có dạng như sau:
- Dòng đầu tiên chứa số nguyên m, số đỉnh của đa giác lồi miêu tả mảnh đất của Bờm.
- Dòng thứ 2 chứa 2m số nguyên cho biết tọa độ các đỉnh của mảnh đất của Bờm. Các đỉnh được liệt kê theo chiều kim đồng hồ.
- Dòng thứ 3 chứa số nguyên n, số đỉnh của đa giác lồi miêu tả mảnh đất của tổ tiên.
- Dòng thứ 4 chứa 2n số nguyên cho biết tọa độ các đỉnh của mảnh đất của tổ tiên Bờm. Các đỉnh được liệt kê theo chiều kim đồng hồ.
Kết qủa
Gồm t dòng, mỗi dòng ghi ra “YES” / “NO” nếu 2 mảnh đất giao nhau / không giao nhau trong test tương ứng.
Giới hạn
- 3 ≤ m, n ≤ 1000
- Tọa độ các đỉnh có giá trị tuyệt đối không vượt quá 1000000000.
- Có 50% số test mà trong đó các số m,n đều có giá trị không vượt quá 100.
Ví dụ
Dữ liệu: 2 3 -6 3 -11 11 -10 6 3 -4 0 -3 5 -7 3 3 -3 4 -3 11 -6 9 3 0 -2 1 0 -2 -1 Kết qủa YES NO
- Người up: paulmcvn
- Nguồn bài: ˆ vnoi.info