Advertisement
LA77

Untitled

Feb 25th, 2025
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. ifstream fin("infasuratoare.in");
  5. ofstream fout("infasuratoare.out");
  6.  
  7. struct point
  8. {
  9.     double x, y;
  10. };
  11.  
  12. const int NMAX = 120005;
  13. int n;
  14. int idx[NMAX];
  15. point arr[NMAX];
  16.  
  17. inline double det(point a, point b, point c)
  18. {
  19.     return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y);
  20. }
  21.  
  22. inline bool Trig(const point &a, const point &b)
  23. {
  24.     return det(arr[1], a, b) > 0;
  25. }
  26.  
  27. int main()
  28. {
  29.     fin >> n;
  30.    
  31.     for(int i = 1; i <= n; ++ i)
  32.         fin >> arr[i].x >> arr[i].y;
  33.        
  34.     int minY = arr[1].y, minpos = 1;    
  35.    
  36.     for(int i = 1; i <= n; ++ i)
  37.     {
  38.         if(minY > arr[i].y)
  39.         {
  40.             minpos = i;
  41.             minY = arr[i].y;
  42.         }
  43.     }
  44.     swap(arr[1], arr[minpos]);
  45.     sort(arr + 2, arr + n + 1, Trig);
  46.  
  47.     idx[1] = 1;
  48.     idx[2] = 2;
  49.    
  50.     int k = 2;
  51.     for(int i = 3; i <= n; ++i)
  52.     {
  53.         while(k > 1 && det(arr[idx[k-1]], arr[idx[k]], arr[i]) <= 0)
  54.             k--;
  55.         idx[++k] = i;
  56.     }
  57.    
  58.     fout << k << '\n';
  59.    
  60.     for(int i = 1; i <= k; ++ i)
  61.         fout << fixed << setprecision(12) << arr[idx[i]].x << ' ' << arr[idx[i]].y << '\n';
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement