| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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ỉ :( |
|||||
RSS