trang chủ / đề bài / icpcwf15_b

Tiểu hành tinh

Đề bài

Mô tả

Năm 2115. Hệ thống trạm chuyển tiếp liên lạc trên các tiểu hành tinh được Bộ Liên lạc Tiểu hành tinh xây dựng từ một thập kỷ trước. Hệ thống vẫn hoạt động tốt, chỉ có một vấn đề nhỏ: có quá nhiều tiểu hành tinh! Những tiểu hành tinh nhỏ không chỉ liên tục gây nhiễu tín hiệu từ các trạm chuyển tiếp mà còn đe dọa mọi phi thuyền bảo trì bay giữa các trạm. Những tiểu hành tinh nhỏ này phải bị tiêu diệt! Liên minh Liên hành tinh Ngăn chặn Thảm họa (ICPC) được giao nhiệm vụ loại bỏ chúng và đã thuê một đội phi công tinh nhuệ. Han Duo là đội trưởng của đội tiêu diệt tiểu hành tinh này. Với kho tên lửa của mình, Han bay qua vành đai tiểu hành tinh và phá hủy mọi tiểu hành tinh mà ICPC coi là phiền toái.

ICPC đang gặp khó khăn về ngân sách. Một hệ quả là Han và đội của anh không có nhiều tên lửa như mong muốn, nên không thể bắn nổ tất cả các tiểu hành tinh gây rắc rối. Nhưng các tiểu hành tinh thì nhỏ còn tên lửa thì rất mạnh. Vì vậy nếu hai tiểu hành tinh ở gần nhau và xếp thẳng hàng hợp lý, có thể tiêu diệt cả hai bằng một quả tên lửa.

Màn hình của Han hiển thị các tiểu hành tinh dưới dạng các đa giác lồi đơn hai chiều không xoay, mỗi đa giác chuyển động với một vận tốc không đổi. Han quyết định rằng thời điểm tốt nhất để bắn hai tiểu hành tinh là khi phần chồng lên nhau (phần giao) của hai đa giác có diện tích lớn nhất. Ví dụ, hình dưới minh họa ví dụ thứ nhất: hai tiểu hành tinh cùng vị trí của chúng sau mỗi giây. Hai tiểu hành tinh bắt đầu chạm nhau sau 3 giây và diện tích phần chồng lên nhau lớn nhất đạt được tại một thời điểm giữa giây thứ 4 và giây thứ 5.

Hình: ví dụ thứ nhất. Hai tiểu hành tinh (tô xám) tại thời điểm 0 với vectơ vận tốc, và các vị trí sau mỗi giây (nét đứt) trên đường đi cắt nhau của chúng.

Tính thời điểm hai tiểu hành tinh chồng lên nhau nhiều nhất cần lập trình một chút, nhưng tiếc là Han đã ngủ gật trong gần hết các giờ học lập trình ở học viện bay. Đó là lúc bạn xuất hiện.

Dữ liệu vào

Dữ liệu vào gồm mô tả của hai tiểu hành tinh. Mỗi mô tả có dạng

nx1y1x2y2…xnynvxvy

trong đó n là số đỉnh, (xi,yi) là tọa độ các đỉnh của tiểu hành tinh trên màn hình của Han, cho theo chiều kim đồng hồ, và vx, vy là vận tốc theo phương x và phương y (đơn vị trên giây) của tiểu hành tinh. Các giá trị xi,yi cho vị trí của tiểu hành tinh tại thời điểm t=0, và tại thời điểm này hai đa giác không cắt nhau cũng không chạm nhau.

Dữ liệu ra

In ra thời điểm (tính bằng giây) mà phần giao của hai đa giác có diện tích lớn nhất; nếu có nhiều thời điểm như vậy, in thời điểm sớm nhất. Nếu hai đa giác không bao giờ chồng lên nhau nhưng có chạm nhau, coi việc chạm nhau là giao nhau với diện tích phần chung bằng 0 và in thời điểm chạm nhau sớm nhất. Nếu hai đa giác không bao giờ chồng lên nhau hay chạm nhau, in ra never. Chỉ xét các thời điểm dương. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−3.

Ràng buộc

  • 3≤n≤10.
  • −10000≤xi,yi≤10000.
  • −100≤vx,vy≤100.
  • Mỗi cạnh của một tiểu hành tinh dài không quá 500.
  • Mọi số trong dữ liệu vào đều là số nguyên.

Ví dụ

Input Output Giải thích
6 3 2 2 4 3 6 6 6 7 4 6 2 2 2
4 18 5 22 9 26 5 22 1 -2 1
4.193518 Đây là hai tiểu hành tinh trong hình: lục giác chuyển động với vận tốc (2,2), hình vuông với vận tốc (−2,1). Chúng chạm nhau sau 3 giây và phần chung lớn nhất đạt được tại khoảng 4,1935 giây.
4 0 0 0 2 2 2 2 0 -1 1
4 10 0 10 2 12 2 12 0 1 1
never Hai hình vuông chuyển động ra xa nhau theo phương x và có cùng vận tốc theo phương y, nên không bao giờ chạm nhau.
4 0 0 0 10 10 10 10 0 0 0
4 13 5 13 8 14 8 14 5 -2 0
2.000000 Hình chữ nhật nhỏ 1×3 đi vào hình vuông 10×10 đứng yên: từ t=1,5 đến t=2 phần chung tăng dần, từ t=2 đến t=6,5 hình chữ nhật nằm trọn trong hình vuông (diện tích phần chung bằng 3, lớn nhất). Thời điểm sớm nhất là 2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0