trang chủ / đề bài / icpc21_bt_g

Khu vườn

Đề bài

Mô tả

Trước nhà Alice có một bãi cỏ với nhiều bông hoa đẹp. Alice muốn rào tất cả các bông hoa lại để làm khu vườn của mình.

Bãi cỏ là một mặt phẳng hai chiều, trên đó có m bông hoa, bông hoa thứ j nằm ở điểm nguyên (xj,yj). Trên bãi cỏ còn có n cọc gỗ, cọc thứ i nằm ở điểm nguyên (Xi,Yi).

Alice muốn khu vườn là một đa giác lồi, nghĩa là nếu muốn đi từ một điểm đến một điểm khác trong vườn, cô có thể đi theo đường thẳng mà không ra khỏi vườn. Khu vườn phải có diện tích dương và mọi đỉnh của nó phải là các cọc gỗ trên bãi cỏ. Mọi bông hoa phải nằm thực sự bên trong khu vườn, nghĩa là không bông hoa nào được nằm ngoài khu vườn hay nằm trên đường biên của nó.

Alice cần hàng rào để bao quanh khu vườn và muốn tổng độ dài hàng rào là nhỏ nhất. Nếu đặt hàng rào giữa cọc thứ a và cọc thứ b, cô cần (Xa−Xb)2+(Ya−Yb)2 đơn vị độ dài hàng rào.

Với mỗi cọc i, Alice muốn biết: nếu khu vườn phải dùng cọc thứ i làm một trong các đỉnh thì cần ít nhất bao nhiêu hàng rào? Hãy giúp cô.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n là số cọc gỗ.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên Xi, Yi là vị trí cọc thứ i.
  • Dòng tiếp theo chứa số nguyên m là số bông hoa.
  • m dòng tiếp theo, dòng thứ j chứa hai số nguyên xj, yj là vị trí bông hoa thứ j.

Dữ liệu đảm bảo không có ba cọc gỗ nào thẳng hàng và mọi vị trí của hoa và cọc gỗ đôi một khác nhau.

Dữ liệu ra

In ra n số thực trên một dòng, cách nhau bởi dấu cách. Số thứ i là độ dài hàng rào nhỏ nhất nếu Alice dùng cọc thứ i làm một đỉnh của khu vườn; nếu không thể rào khu vườn có cọc thứ i làm đỉnh, in ra −1.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá 10−6: nếu đáp án của bạn là a và đáp án của ban giám khảo là b, đáp án được chấp nhận khi |a−b|max(1,|b|)≤10−6.

Ràng buộc

  • 1≤n≤100.
  • −109≤Xi,Yi≤109.
  • 1≤m≤105.
  • −109≤xj,yj≤109.

Ví dụ

Input Output Giải thích
5
0 0
2 2
-2 -2
2 -2
-2 2
4
1 1
-1 -1
1 -1
-1 1
-1 16 16 16 16 Cọc (0,0) nằm giữa các bông hoa nên không thể là đỉnh. Bốn cọc còn lại tạo thành hình vuông cạnh 4 chứa mọi bông hoa bên trong, chu vi 16.
3
0 0
4 0
0 4
1
2 0
-1 -1 -1 Bông hoa nằm trên cạnh nối (0,0) và (4,0) của tam giác duy nhất, nên không thể rào.

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