Đề bài: $\href{https://codeforces.com/problemset/problem/485/B}{Đây}$
Tóm tắt: Cho n điểm trên tọa độ Oxy, tìm diện tích hình vuông nhỏ nhất chứa tất cả các điểm đó (các điểm có thể nằm bên trong hoặc trên biên)
Lời giải: Chiếu các điểm đó lần lượt trên Ox, Oy ta lần lượt xác định được giới hạn của các điểm đó, từ đó tìm ra được độ dài tối thiểu của hình vuông.
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define inf 1000000000000000000
- ll maaxX,miinX,maaxY,miinY;
- struct cap{
- ll x;
- ll y;
- };
- int main(){
- maaxX=maaxY=-inf;
- miinX=miinY=inf;
- ll n;
- cin>>n;
- cap a[n];
- ll i;
- for(i=0;i<n;i++){
- cin>>a[i].x>>a[i].y;
- maaxX = max(maaxX,a[i].x);
- maaxY = max(maaxY,a[i].y);
- miinX=min(miinX,a[i].x);
- miinY=min(miinY,a[i].y);
- }
- ll res;
- res=max((ll)(maaxX-miinX),(ll)(maaxY-miinY));
- res=res*res;
- cout<<res;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét