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ó bông hoa, bông hoa thứ nằm ở điểm nguyên . Trên bãi cỏ còn có cọc gỗ, cọc thứ nằm ở điểm nguyên .
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ứ và cọc thứ , cô cần đơn vị độ dài hàng rào.
Với mỗi cọc , Alice muốn biết: nếu khu vườn phải dùng cọc thứ 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 là số cọc gỗ.
- dòng tiếp theo, dòng thứ chứa hai số nguyên , là vị trí cọc thứ .
- Dòng tiếp theo chứa số nguyên là số bông hoa.
- dòng tiếp theo, dòng thứ chứa hai số nguyên , là vị trí bông hoa thứ .
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 số thực trên một dòng, cách nhau bởi dấu cách. Số thứ là độ dài hàng rào nhỏ nhất nếu Alice dùng cọc thứ làm một đỉnh của khu vườn; nếu không thể rào khu vườn có cọc thứ làm đỉnh, in ra .
Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá : nếu đáp án của bạn là và đáp án của ban giám khảo là , đáp án được chấp nhận khi .
Ràng buộc
- .
- .
- .
- .
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 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 chứa mọi bông hoa bên trong, chu vi . |
| 3 0 0 4 0 0 4 1 2 0 |
-1 -1 -1 | Bông hoa nằm trên cạnh nối và của tam giác duy nhất, nên không thể rào. |
Bình luận