Mảnh đất tổ tiên

View as PDF

Submit solution


Points: 0.53 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
ˆ vnoi.info
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

Input

Dòng đầu tiên chứa số nguyên ~t~, cho biết số lượng test ~(t \leq 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 ~2_m~ 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 ngược 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 ~2_n~ 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 ngược kim đồng hồ.

Output

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 \leq m~, ~n \leq 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~.

Sample Input

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

Sample Output

YES
NO

Comments

Please read the guidelines before commenting.


There are no comments at the moment.