Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Bus Terminals - Mạng l­ưới xe buýt
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526

Bài toán

Thành phố Yong-In có kế hoạch xây dựng một mạng lưới xe buýt gồm N bến đỗ. Mỗi bến đỗ xe nằm ở một góc phố. Yong-In là một thành phố hiện đại nên các con đường trong thành phố tạo thành một lưới ô vuông bằng nhau. Hai trong số các bến đỗ đó được chọn làm trung tâm là H1H2. Hai bến xe trung tâm được nối với nhau bằng một tuyến xe buýt trực tiếp và N - 2 bến xe còn lại chỉ được nối trực tiếp với H1 hoặc H2 (nhưng không đồng thời nối trực tiếp với cả hai bến xe trung tâm) mà không nối trực tiếp với bến xe nào khác

Khoảng cách giữa hai bến xe bất kỳ là đường đi ngắn nhất giữa các con phố. Nghĩa là, nếu một bến xe có tọa độ là (x, y), thì khoảng cách giữa hai bến xe (x1, y1) và (x2, y2) . Nếu hai bến xe AB cùng nối với bến xe trung tâmH1, thì khoảng cách giữa hai bến xe này bằng tổng khoảng cách từ A đến H1 và từ H1 đến B. Nếu hai bến xe AB nối với hai bến xe trung tâm khác nhau, ví dụ, A nối với H1B nối với H2, thì khoảng cách giữa hai bến xe này là tổng khoảng cách từ A đến H1, từ H1 đến H2, và từ H2 đến B.

Ban quản lý dự án của thành phố Yong-In muốn đảm bảo chắc chắn rằng tất cả mọi người dân trong thành phố có thể đi đến bất cứ điểm nào trong thành phố một cách nhanh nhất. Do đó, ban quản lý muốn chọn hai bến xe làm bến xe trung tâm sao cho khoảng cách lớn nhất giữa hai bến xe bất kỳ là ngắn nhất có thể được.

Một cách chọn P (chọn hai bến xe trung tâm) được coi là tối ưu hơn cách chọn Q nếu khoảng cách lớn nhất giữa hai bến xe ở cách chọn P ngắn hơn ở cách chọn Q. Hãy viết chương trình tính khoảng cách lớn nhất giữa hai bến xe buýt trong cách chọn P.

INPUT

Dòng đầu tiên chứa một số nguyên dương N, 2 ≤N ≤ 500, chỉ số bến xe buýt. Mỗi dòng trong số N dòng tiếp theo chứa tọa độ của các bến xe. Tọa độ x và y đều là các số nguyên dương nhỏ hơn 5000. Hai bến xe buýt khác nhau phải nằm trên  hai vị trí khác nhau.

OUTPUT

Output là một dòng chứa một số nguyên dương chỉ khoảng cách lớn nhất giữa hai bến xe buýt

Ví dụ

INPUT và OUTPUT

Hình dưới minh họa mạng lưới xe buýt trong ví dụ trên. Nếu trong ví dụ 1, bến xe 3 và 4 được chọn làm bến trung tâm, thì khoảng cách lớn nhất giữa hai bến xe 2 và 5 hoặc giữa 2 và 1 là khoảng cách lớn nhất. Không có cách lựa chọn bến xe trung tâm tối ưu hơn và khoảng cách lớn nhất lúc này là 20.

Với mạng lưới xe buýt trong ví dụ 2, nếu bến xe 5 và 6 được chọn là bến xe trung tâm, thì khoảng cách giữa hai bến xe 2 và 7 là khoảng cách lớn nhất. Không có cách lựa chọn bến xe trung tâm tối ưu hơn và khoảng cách lớn nhất lúc này là 25.

Cho điểm

Nếu chương trình của bạn cho kết quả đúng trong khoảng thời gian cho phép, bạn sẽ giành được điểm tối đa, ngược lại bạn sẽ đượcc 0 điểm.
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556