//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Khung ảnh

Sau 6h làm bài thi căng thẳng, BB là thí sinh có điểm cao nhất trong kỳ thi Icamp 4. Phần thưởng dành cho cậu là một tấm ảnh có kèm chữ ký tặng của Hoa hậu Việt Nam 2006 – Mai Phương Thúy. Rất háo hức với phần thưởng đặc biệt này, BB muốn tìm ngay một chiếc khung thật đẹp để lồng tấm ảnh vào.

Tuy nhiên, tấm ảnh Hoa hậu mà BB nhận được từ ban tổ chức kỳ thi Icamp 4 lại rất đặc biệt, nó không có hình chữ nhật như những tấm ảnh bình thường mà lại là 1 hình đa giác lồi. Rất may mắn, BB thấy ở hiệu ảnh cũng có một khung ảnh hình đa giác lồi, tuy nhiên cậu không chắc tấm ảnh có thể lồng vừa vào khung nên muốn bạn xác định giúp.

BB sẽ mô tả tấm ảnh và khung cho bạn bằng cách chỉ ra tọa độ các đỉnh của 2 đa giác này trong hệ trục tọa độ Descartes. Tấm ảnh là đa giác lồi N đỉnh, đỉnh thứ i có tọa độ là (xi, yi). Khung ảnh là đa giác lồi M đỉnh, đỉnh thứ k có tọa độ là (xk, yk). Thứ tự của các đỉnh đa giác được cho cùng chiều kim đồng hồ. Cả tấm ảnh và khung ảnh đều được đặt trong cùng một hệ trục tọa độ và ban đầu có thể chồng lên nhau hoặc không.

Bạn cần xác định xem có thể lồng được bức ảnh vào khung hay không, có nghĩa là xác định xem có tồn tại một phép tịnh tiến nào để tịnh tiến đa giác biểu diễn cho tấm ảnh sao cho đa giác này hoàn toàn nằm trong đa giác biểu diễn cho khung ảnh.

InputFRAME.INP

  • Dòng đầu ghi số nguyên dương N là số đỉnh của tấm ảnh.
  • Dòng thứ i trong số N dòng tiếp theo ghi 2 số nguyên xi, yi là tọa độ đỉnh thứ i của tấm ảnh.
  • Dòng tiếp theo ghi số nguyên dương M là số đỉnh của khung ảnh.
  • Dòng thứ k trong số M dòng cuối ghi 2 số nguyên xk, yk là tọa độ đỉnh thứ k của khung ảnh.

Output:            FRAME.OUT

  • Dòng đầu ghi “YES” / “NO” ứng với có thể / không thể lồng được bức ảnh vào khung.
  • Nếu dòng đầu ghi “YES”, dòng thứ hai ghi 2 số thực Dx, Dy ứng với cần phải tịnh tiến tấm ảnh theo vector (Dx, Dy) để nằm hoàn toàn trong khung ảnh.

Giới hạn:

  • 3 ≤ N, M ≤ 1000
  • Các tọa độ đỉnh của 2 đa giác là các số nguyên có trị tuyệt đối không quá 109
  • Dx, Dy cần ghi với độ chính xác 3 chữ số sau dấu phẩy.
  • Thời gian: 1 s/test
  • Bộ nhớ: 1 MB
  • Có 30% số test có N, M ≤ 10

Ví dụ:

FRAME.INP FRAME.OUT
4

3 1

2 3

5 3

4 1

3

0 0

4 4

6 0

YES

0.000 -1.000

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: