Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKLAND - Mảnh đất tổ tiên

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

Được gửi lên bởi:Jimmy
Ngày:2008-01-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ˆ vnoi.info

hide comments
2021-08-05 03:10:28
IDOL NGUYEN XUAN HIEU HAI PHONG VO DOI
EZ GAME EZ LIFE
ALL HAIL THE KING
2020-04-11 13:02:37
int 72.73
long long 9.09
double 100
????
2019-01-09 04:45:21
Test hơi lỏng, 1 điểm của H1 có trong H2 hoặc ngược lại => YES.
Thêm trường hợp có hai điểm trở lên của một hình này nằm trên hình kia (trên 1 cạnh) cứ tham cho là YES cũng AC. >:))
2017-06-02 15:17:09
dễ VL
2016-07-16 05:30:53
for trâu từng điểm đa giác 1, 2 check xem nằm trong đa giác còn lại không -> AC
không có test 2 mảnh đất chứa nhau =)) may quá :v
2015-11-05 07:42:17 Hacking to the Gate
Separating Axis Theorem
2014-12-18 05:55:41 ðẹp trai bẩm sinh
Bọc lồi graham 2 đa giác.

- Với mỗi đỉnh của đa giác 1 kiểm tra xem nó có nằm trong đa giác 2 ko, và ngược lại, nếu có YES => được 90.91
- Ngược lại, gọi D1 = S1+S2, và bọc lồi graham toàn bộ đỉnh của 2 đa giác. D2 là diện tích đa giác mới. Nếu D2<D1 thì YES, ngược lại NO => 100

Ví dụ đơn giản dễ thấy nhất là google "ngôi sao 6 cánh"
2014-11-14 03:25:08 NhiVD
Duyệt kha khá trâu mà tại sao 86 điểm z trời :'(
2014-06-18 09:56:11 ๖ۣۜPublic °°
bài này tung hỏa mù nhiều quá, tuy nhiên làm mất có 5p à
2014-02-11 04:50:29 a;slkfjasl;fkj
nếu 2 tam giác mà có chung 1 cạnh, còn phần còn lại của 2 tam giác riêng biệt thì nó có gọi là giao nhau ko nhỉ :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.