Đêm qua tôi thấy bạn chạy
Trên những cánh đồng rộng mở của ân sủng
Bạn không còn tan vỡ hay đau đớn nữa.[^1]
Bạn tìm thấy một cánh đồng mênh mông, nơi bạn quên đi quá khứ từng tan vỡ và đau khổ. Bạn chạy như một đứa trẻ trong ân huệ của Chúa.
Tuy nhiên, bạn phát hiện một vấn đề: trong cánh đồng có một số hẻm vực. Bạn luôn có nguy cơ rơi xuống một hẻm vực. Để tiếp tục chạy tự do, bạn quyết định dùng một số hàng rào bao quanh các hẻm vực này.
Ta có thể bỏ qua chiều rộng của hẻm vực và coi mỗi hẻm vực là một đoạn thẳng. Các đoạn thẳng này có thể giao nhau, còn hàng rào của bạn phải là một hoặc nhiều đường cong kín không tự cắt và đôi một không giao nhau, sao cho mỗi hẻm vực nằm hoàn toàn trong miền kín được bao bởi một trong các đường cong kín.
Tất nhiên, hàng rào tiêu tốn tài nguyên, và lượng tài nguyên tiêu tốn tỉ lệ thuận với chiều dài hàng rào. Bạn muốn tối thiểu hóa tổng tài nguyên tiêu tốn, vì vậy bạn muốn tìm cận dưới đúng của tổng chiều dài hàng rào. Nói cách khác, bạn muốn tìm số thực $x$ lớn nhất sao cho không tồn tại phương án nào có tổng chiều dài hàng rào nhỏ hơn $x$.
Dữ liệu vào
Đọc dữ liệu từ tệp fields.in.
Dòng đầu tiên của tệp đầu vào chứa một số nguyên $n$, là số hẻm vực.
Tiếp theo là $n$ dòng, dòng thứ $i$ chứa bốn số nguyên $a_i,b_i,c_i,d_i$, biểu thị hẻm vực thứ $i$ là đoạn thẳng nối hai điểm $(a_i,b_i)$ và $(c_i,d_i)$. Đảm bảo hai đầu mút không trùng nhau và các đoạn thẳng khác nhau không có chung đầu mút. Đảm bảo không có ba điểm nào thẳng hàng.
Dữ liệu ra
Ghi kết quả vào tệp fields.out.
In ra một dòng chứa một số thực, là cận dưới đúng của tổng chiều dài hàng rào. Giá trị nhỏ hơn giữa sai số tuyệt đối và sai số tương đối của đáp án của bạn so với đáp án chuẩn không được vượt quá $10^{-6}$.
Ví dụ
Dữ liệu vào 1
1 0 0 0 1
Dữ liệu ra 1
2.00000000
Ghi chú
Hình chữ nhật có bốn đỉnh $(-0.01,-0.01),(-0.01,1.01),(0.01,1.01),(0.01,-0.01)$ chứa hoàn toàn đoạn thẳng đầu vào và có tổng chiều dài $2.08$, lớn hơn cận dưới đúng một chút.
Ta có thể chứng minh rằng không tồn tại phương án có chiều dài đúng bằng $2$. Bằng cách liên tục “siết” hình vuông về phía đoạn thẳng đầu vào, ta có thể xây dựng phương án có chiều dài bằng bất kỳ giá trị nào lớn hơn $2$.
Dữ liệu vào 2
4 -1 7 0 7 0 0 0 1 2 -3 5 5 2 2 6 -1
Dữ liệu ra 2
23.563573998194637061425470524757
Ghi chú
Hình dưới đây biểu diễn các đoạn thẳng đầu vào; lưu ý rằng các đoạn thẳng có thể giao nhau:
Hình 1: Giải thích ví dụ 2
Bằng cách liên tục “tiến sát” các đường cong màu đỏ này, ta có thể xây dựng phương án có tổng chiều dài bằng bất kỳ giá trị nào lớn hơn đáp án. Lưu ý rằng, từ ví dụ 1, ta dễ dàng biết đoạn thẳng màu đỏ ở góc trên bên trái được tính hai lần.
Dữ liệu vào 3
4 -1 1 -1 3 0 4 2 4 3 1 3 3 0 0 2 0
Dữ liệu ra 3
13.656854249492380195206754896839
Ghi chú
Đáp án là $8+4\sqrt{2}$.
Giải thích được thể hiện trong hình:
Hình 2: Giải thích ví dụ 3
Bằng cách liên tục “tiến sát” các đường cong màu đỏ này, ta có thể xây dựng phương án có tổng chiều dài bằng bất kỳ giá trị nào lớn hơn $8+4\sqrt{2}$.
Ví dụ 4
Xem fields/fields4.in và fields/fields4.ans trong thư mục của thí sinh.
Giới hạn
Với $5\%$ dữ liệu, đảm bảo $1\le n\le 1$.
Với $10\%$ dữ liệu, đảm bảo $1\le n\le 2$.
Với $15\%$ dữ liệu, đảm bảo $1\le n\le 10$.
Với $30\%$ dữ liệu, đảm bảo $1\le n\le 15$.
Với $45\%$ dữ liệu, đảm bảo $1\le n\le 30$.
Với $55\%$ dữ liệu, đảm bảo $1\le n\le 60$.
Với $65\%$ dữ liệu, đảm bảo $1\le n\le 120$.
Với $75\%$ dữ liệu, đảm bảo $1\le n\le 200$.
Với $10\%$ dữ liệu khác, đảm bảo đáp án bao gồm nhiều nhất hai đường cong.
Với $100\%$ dữ liệu, đảm bảo $1\le n\le 250$, $0\le |a_i|,|b_i|,|c_i|,|d_i|\le 10^9$. Đảm bảo hai đầu mút không trùng nhau và các đoạn thẳng khác nhau không có chung đầu mút. Đảm bảo không có ba điểm nào thẳng hàng.
[^1]: Lời bài hát trong đề trích từ Open Fields of Grace do Jackie Evancho thể hiện, được sáng tác bởi Lisa Venkatrathnam và Paul Sumares.