khôngtên
18-08-2003, 11:17
Mạng lưới xe buýt (Bus Terminals)
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à H1 và H2. 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) là . Nếu hai bến xe A và B 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 A và B nối với hai bến xe trung tâm khác nhau, ví dụ, A nối với H1 và B 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.
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à H1 và H2. 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) là . Nếu hai bến xe A và B 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 A và B nối với hai bến xe trung tâm khác nhau, ví dụ, A nối với H1 và B 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.