Ông Hàm là chủ một trang trại nuôi bò có dạng hình đa giác lồi đỉnh. Cổng của trang trại là một cạnh của đa giác, kí hiệu là , với là hai đỉnh của đa giác. Mùa đông lạnh giá đang tới, ông xây dựng hệ thống sưởi cho đàn bò của mình như sau:
Đầu tiên ông đặt tại mỗi đỉnh đa giác một cột đèn sưởi, dây điện nói liên thông giữa một số cột đèn với nhau. Vì lý do an toàn nên ông thiết kế dây điện chỉ chạy trên các đoạn thẳng men theo các cạnh của đa giác mà không đi vào bên trong trang trại và không chạy ngang qua cạnh . Ông đặt hai cầu dao tổng tại hai đỉnh nhằm đưa nguồn điện từ bên ngoài vào hệ thống đèn sưởi bắt đầu từ . Đề tiết kiệm chỉ phí, ngoài cạnh ông không cho chạy dây qua một cạnh dài nhất trong số các cạnh còn lại của đa giác. Sau khi hoàn thành ông tính ra tổng độ dài dây điện sử dụng là khá lớn, nên ông quyết định tiết kiệm tối đa dây điện sử dụng trong việc dẫn nguồn điện vào.
Nhằm đảm bảo nguồn điện liên tục cho hệ thống đèn sưởi của trang trại, ông chủ trang trại tìm cách đi dây sao cho tất cả đèn sưởi đều có hai nguồn điện đi tới. Trong trường hợp có một nguồn điện bị mất thì vẫn còn một nguồn điện dự phòng cung cấp. Ông quyết định phương án đi dây điện ngầm từ hai nguồn điện đến hai đỉnh , ký hiệu vị trí hai nguồn điện đó là và . Lưu ý rằng dây điện không nhất thiết phải chạy riêng rẽ trực tiếp từ từng nguồn điện đến hai đỉnh , mà có thể đi chung và rẽ nhánh ở một số điểm trên đường đi, nhưng phải đảm bảo mỗi đỉnh đều có cách dẫn điện từ cả hai nguồn theo hệ thống dây điện mới thiết kế. Do đường điện đi ngầm nên các dây điện có thể chạy bên trong trang trại hoặc trên cạnh . Ngoài ra ông còn phát hiện ra bốn điểm , có vị trí liên hệ đặc biệt với nhau (được mô tả chỉ tiết trong phần ràng buộc của bài toán).
Hình vẽ dưới đây minh họa một cách đi dây điện. Đa giác biểu diễn trang trại bao gồm các đỉnh với là cổng và là cạnh dài nhất khác cạnh nên không được nối. Các đoạn nét liền mô tả đi dây dọc theo các cạnh của đa giác. Các đoạn nét đứt mô tả việc đi dây từ hai nguồn tới hai đỉnh . Bốn điểm tạo thành một hình vuông và là điểm rẽ nhánh. Tổng độ dài lượng dây điện sử dụng trong hình vẽ bằng tổng độ dài các đoạn:
Yêu cầu: Biết tọa độ vị trí các đỉnh của đa giác và tọa độ vị trí của hai nguồn điện, hãy giúp ông Hàm thiết kế đi dây điện sao cho tổng độ đài dây điện sử dụng là ít nhất. Độ dài dây điện được tính bằng tổng độ dài đoạn đường mà dây đi qua, quanh các cạnh của đa giác và từ hai nguồn điện đến .
Dữ liệu vào:
Dòng thứ nhất chứa một số nguyên là số đỉnh của đa giác;
Dòng thứ hai chứa hai số nguyên là tọa độ của đỉnh ;
Dòng thứ ba chứa hai số nguyên là tọa độ của đỉnh ;
Mỗi dòng trong số dòng tiếp theo chứa hai số nguyên là tọa độ một trong số đỉnh còn lại của đa giác.
Dòng cuối cùng chứa bốn số nguyên là các tọa độ tương ứng của vị trí hai nguồn điện và .
Lưu ý: Trong dữ liệu vào, các đỉnh của đa giác không nhất thiết được liệt kê theo một thứ tự nhất định cho trước. Dữ liệu đảm bảo không có ba đỉnh nào của đa giác thẳng hàng. Tất cả tọa độ cho trong dữ liệu vào nằm trong khoảng . Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số duy nhất là độ dài dây điện tìm được. Số in ra cần làm tròn đến chữ số sau dấu phẩy.
Giới hạn:
Có số lượng test ứng với số điểm của bài thỏa mãn điều kiện: , các tọa độ đỉnh của đa giác được liệt kê xuôi chiều kim đồng hỗ theo trình tự xuất hiện trong file dữ liệu vào, và bốn vị trí cùng nằm trên một đường thăng;
số lượng test khác ứng với số điểm của bài thỏa mãn điều kiện: , các tọa độ của nằm trong khoảng , và đường thẳng đi qua hai điểm là đường trung trực của đoạn thắng , đồng thời thuộc cùng một nửa mặt phẳng tạo bởi đường thẳng đi qua ;
số lượng test khác ứng với số điểm của bài thỏa mãn điều kiện: , và đường thẳng đi qua hai điểm là đường trung trực của đoạn thăng , đồng thời thuộc cùng một nửa mặt phẳng tạo bởi đường thẳng đi qua ;
số lượng test còn lại ứng với số điểm của bài thỏa mãn điều kiện: , và bốn đỉnh tạo thành một hình vuông.
Ví dụ:
Dữ liệu vào:
4
4 0
0 0
0 4
4 4
-1 0 5 0
Dữ liệu ra:
14.00
Giải thích:
Trong ví dụ trên, các đoạn dây điện nối dọc theo các cạnh của đa giác bao gồm: nối
với và nối với . Ngoài cạnh , một cạnh dài nhât không được nối dây là cạnh . Cách
kết nối từ vị trí hai nguôn điện và tới và sử dụng ít dây điện nhất là nối với , nối với ,
và nôi với .
