Chủ Nhật, 29 tháng 11, 2020

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)

 Đề 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:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define inf 1000000000000000000
  5. ll maaxX,miinX,maaxY,miinY;
  6. struct cap{
  7. ll x;
  8. ll y;
  9. };
  10. int main(){
  11. maaxX=maaxY=-inf;
  12. miinX=miinY=inf;
  13. ll n;
  14. cin>>n;
  15. cap a[n];
  16. ll i;
  17. for(i=0;i<n;i++){
  18. cin>>a[i].x>>a[i].y;
  19. maaxX = max(maaxX,a[i].x);
  20. maaxY = max(maaxY,a[i].y);
  21. miinX=min(miinX,a[i].x);
  22. miinY=min(miinY,a[i].y);
  23. }
  24. ll res;
  25. res=max((ll)(maaxX-miinX),(ll)(maaxY-miinY));
  26. res=res*res;
  27. cout<<res;
  28. return 0;
  29. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...