Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow VOI (thi quốc gia) arrow 2010 arrow Bus Terminals - Mạng l­ưới xe buýt
Bus Terminals - Mạng l­ưới xe buýt In E-mail
(0 votes)
Người viết: Ngô Minh Đức   
21/04/2008

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.
 
< Trước   Tiếp >