Problem
Bộ Giao thông vận tải đường bộ đã quyết định xây dựng một văn phòng mới cho mình. Vì bộ trưởng thường xuyên đi thị sát các tuyến đường quan trọng nhất nên người ta quyết định rằng văn phòng của bộ không nên đặt quá xa các tuyến đường đó.
Dọc hàng quan trọng nhất là các đường thẳng trên mặt phẳng. Bộ muốn chọn địa điểm đặt văn phòng sao cho khoảng cách từ văn phòng đến đường cao tốc là ngắn nhất có thể.
Bạn cần viết một chương trình, với vị trí của các đường cao tốc quan trọng nhất, xác định vị trí tối ưu của ngôi nhà cho văn phòng Bộ Giao thông Vận tải Đường bộ.
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa một số nguyên duy nhất n — số lượng dấu vết quan trọng nhất (1 ≤ n ≤ 104 ).
N dòng tiếp theo mô tả dấu vết. Mỗi dấu vết được mô tả bởi bốn số nguyên x1, y1, x2 và y2 và là một đường thẳng đường thẳng đi qua các điểm (x1, y1) và (x2, y2) . Tọa độ của các điểm đã cho không vượt quá 104 về giá trị tuyệt đối. Dấu chấm (x1 , y1) và (x2 , y2) không khớp với bất kỳ dòng nào.
Đầu ra
Tệp đầu ra phải chứa hai số thực được phân tách bằng dấu cách: tọa độ của điểm nơi sẽ xây dựng văn phòng của Bộ Giao thông Vận tải Đường bộ. Các tọa độ modulo không được vượt quá 109, đảm bảo rằng tồn tại ít nhất một câu trả lời như vậy. Nếu có nhiều câu trả lời tối ưu, hãy in bất kỳ câu trả lời nào trong số chúng.
Câu trả lời phải có lỗi tuyệt đối hoặc tương đối không quá 10&trừ 6, nghĩa là như sau. Đặt khoảng cách tối đa từ điểm được vẽ đến một dấu vết nào đó bằng x và trong câu trả lời đúng, nó bằng y. Câu trả lời sẽ được tính nếu giá trị của biểu thức | x .trừ; y | / tối đa(1, |y| ) không vượt quá 10−6.
| Đầu vào |
Đầu ra |
|
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
|
0,5000000004656613 0,4999999995343387 |
|
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
|
4040.9996151750674 12003.999615175067 |
Olympic cá nhân, Olympic toàn Nga dành cho học sinh, Giai đoạn khu vực, 2011, ngày thứ 2, Bài toán D