Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstddef>
  3. #include <vector>
  4. #include <set>
  5.  
  6. using Point = std::pair<long long, long long>;
  7. int sign(long long sp) {
  8.   if (sp > 0) return 1;
  9.   if (sp < 0) return -1;
  10.   return 0;
  11. }
  12.  
  13. long long rotate_predicate(Point a, Point b, Point c) {
  14.   return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
  15. }
  16.  
  17. int sign_rotate_predicate(Point a, Point b, Point c) {
  18.   return sign(rotate_predicate(a, b, c));
  19. }
  20.  
  21. std::set<Point> result;
  22. void quick_hull(const std::vector<Point>& pts, Point L, Point R, int side) {
  23.   size_t maxInd = -1;
  24.   long long maxDist = 0;
  25.  
  26.   for (size_t i = 0; i < pts.size(); i++) {
  27.     long long curDist = rotate_predicate(L, R, pts[i]);
  28.  
  29.     if (sign(curDist) == side && abs(curDist) > maxDist) {
  30.       maxDist = abs(curDist);
  31.       maxInd = i;
  32.     }
  33.   }
  34.  
  35.   if (maxInd == -1) {
  36.     result.insert(L);
  37.     result.insert(R);
  38.     return;
  39.   }
  40.  
  41.   int sign = sign_rotate_predicate(L, R, pts[maxInd]);
  42.   quick_hull(pts, L, pts[maxInd], sign);
  43.   quick_hull(pts, pts[maxInd], R, sign);
  44. }
  45.  
  46. int main(void) {
  47.   freopen("hull.in", "r", stdin);
  48.   freopen("hull.out", "w", stdout);
  49.   std::ios_base::sync_with_stdio(0);
  50.  
  51.   std::vector<Point> pts;
  52.   size_t n;
  53.   std::cin >> n;
  54.  
  55.   size_t leftInd = 0, rightInd = 0;
  56.   for (size_t i = 0; i < n; i++) {
  57.     long long x, y;
  58.     std::cin >> x >> y;
  59.     pts.emplace_back(x, y);
  60.  
  61.     if (pts[i] < pts[leftInd]) {
  62.       leftInd = i;
  63.     } if (pts[rightInd] < pts[i]) {
  64.       rightInd = i;
  65.     }
  66.   }
  67.  
  68.   std::vector<Point> hull;
  69.   quick_hull(pts, pts[leftInd], pts[rightInd], 1);
  70.  
  71.   for (auto p = result.begin(); p != result.end(); ++p) {
  72.     hull.push_back(*p);
  73.   }
  74.   result.clear();
  75.  
  76.   quick_hull(pts, pts[leftInd], pts[rightInd], -1);
  77.   for (auto p = result.rbegin(); p != result.rend(); ++p) {
  78.     if (*p == pts[leftInd] || *p == pts[rightInd]) {
  79.       continue;
  80.     }
  81.     hull.push_back(*p);
  82.   }
  83.  
  84.   std::cout << hull.size() << '\n';
  85.   for (auto it = hull.begin(); it != hull.end(); ++it) {
  86.     std::cout << it->first << ' ' << it->second << '\n';
  87.   }
  88.  
  89.   return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement