|
|
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.
Từ tập các bài có trên SPOJ (oi)
2296. Mảnh ðất tổ tiên
Mã bài: NKLAND
|
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: | Ngô Minh Ðức |
| Ngày: | 2008-01-05 |
| Thời gian chạy: | 1s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | ˆ vnoi.info |
|
|
|
|
