MDIST - Khoảng cách xa nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Trên mặt phẳng ~Oxy~ có ~N~ điểm, điểm thứ ~i~ có tọa độ là ~(x_i, y_i)~. Hãy cho biết khoảng cách Manhattan xa nhất giữa hai điểm bất kì trong ~N~ điểm trên.
Ta định nghĩa khoảng cách Manhattan giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~|x1 − x2| + |y1 − y2|~.
Input
- Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 100)~ - số điểm đã cho;
- ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~x_i, y_i\ (−1000 ≤ x_i, y_i ≤ 1000)~ - tọa độ của điểm thứ ~i~.
Output
- In ra một số nguyên duy nhất là khoảng cách Manhattan lớn nhất cần tìm.
Sample
Input #1
2
-1 3
1 1
Output #1
4
Input #2
4
0 0
1 2
1 3
0 5
Output #2
5
Hint
- Ở ví dụ thứ nhất, khoảng cách Manhattan giữa hai điểm là ~|(−1) − 1| + |3 − 1| = 2 + 2 = 4~.
- Ở ví dụ thứ hai, hai điểm ~(0, 0)~ và ~(0, 5)~ có khoảng cách Mantantan lớn nhất.
Problem source: Kc97ble - Free Contest
Bình luận
include <bits/stdc++.h>
using namespace std;
int main() { int n;cin>>n; pair<int,int> a[n] ; for(int i=0;i<n;i++) { cin>>a[i].first>>a[i].second; } int kq=INT_MIN; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { kq=max(kq,abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second)); } } cout<<kq<<endl; }