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:Duc
Ngày:2008-01-05
Thời gian chạy:0.610s
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
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ỉ :(
2012-12-27 01:44:01 Ðẹp trai có gì sai
Bài này mình dùng diện tích, độ phức tạp là O(M*N*T) mà chỉ được có 45,45. Không biết là TLE hay WA nhỉ? :(

Last edit: 2012-12-27 01:44:41
2011-10-26 15:12:27 Noyethug
test quá yếu...........viết sai pt đường thẳng vẫn đc 54.55.....sửa lại => AC........:|.....O(m*n*t) là đủ để AC.....:)
2011-04-12 17:53:54 ðẹp trai bẩm sinh
Đa giác này còn có 3 điểm thẳng hàng nửa :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.