4eyes4u

Untitled

Nov 21st, 2016
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. /*
  2. Andrew's monotone chain convex hull algorithm
  3. O(NlogN)
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef complex<ll> pt;
  11.  
  12. const int N=1e5+10;
  13.  
  14. int n;
  15. vector<pt> t, hull;
  16.  
  17. ll cross (pt a, pt b, pt c)
  18. {
  19.     return imag(conj(b-a)*(c-a));
  20. }
  21.  
  22. bool cmp (const pt &z, const pt &w)
  23. {
  24.     if (real(z)==real(w)) return imag(z)<imag(w);
  25.     return real(z)<real(w);
  26. }
  27.  
  28. void convexHull ()
  29. {
  30.     sort (t.begin(), t.end(), cmp);
  31.  
  32.     for (int i=0; i<2; i++)
  33.     {
  34.         int initSize=hull.size();
  35.         for (auto xt: t)
  36.         {
  37.             while (hull.size()>=initSize+2 && cross(hull[hull.size()-2], hull[hull.size()-1], xt)<=0) hull.pop_back();
  38.             hull.push_back(xt);
  39.         }
  40.  
  41.         hull.pop_back();
  42.         reverse(t.begin(), t.end());
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     scanf ("%d", &n);
  49.     t.resize(n);
  50.     for (int i=0;i<n;i++)
  51.     {
  52.         ll a, b;
  53.         scanf ("%lld%lld", &a, &b);
  54.         t[i]=pt(a, b);
  55.     }
  56.  
  57.     convexHull();
  58.  
  59.     printf ("%d\n", hull.size());
  60.     for (auto xt: hull) printf ("%lld %lld\n", real(xt), imag(xt));
  61.  
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment