Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <string>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stack>
  9. #define pb push_back
  10. #define ll long long
  11. using namespace std;
  12.  
  13. double pi = acos(-1);
  14.  
  15. struct point {
  16.     int x, y;
  17. };
  18.  
  19. int cross(const point &a, const point &b, const point &c) {
  20.     return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
  21. }
  22.  
  23. bool cmp(const point &a, const point &b) {
  24.     return (a.x < b.x) || (a.x == b.x && a.y < b.y);
  25. }
  26.  
  27. int main() {
  28.  
  29.     //freopen("convex.in", "r", stdin);
  30.     //freopen("convex.out", "w", stdout);
  31.     freopen("input.txt", "r", stdin);
  32.     freopen("output.txt", "w", stdout);
  33.     int n;
  34.     cin >> n;
  35.     vector <point> s(n);
  36.     for(int i = 0; i < n; ++i)
  37.         cin >> s[i].x >> s[i].y;
  38.     if(n == 1) {
  39.         cout << "1" << endl;
  40.         cout << s[0].x << " " << s[0].y << endl;
  41.         return 0;
  42.     }
  43.     if(n == 2) {
  44.         if(s[0].x == s[1].x && s[0].y == s[0].y) {
  45.         cout << "1" << endl;
  46.         cout << s[1].x << " " << s[1].y << endl;
  47.         return 0;
  48.         }
  49.     }
  50.     sort(s.begin(), s.end(), cmp);
  51.     point p1 = s[0], p2 = s[s.size() - 1];
  52.     vector <point> up, down;
  53.     up.pb(p1);
  54.     down.pb(p1);
  55.  
  56.     for(int i = 1; i < n - 1; ++i) {
  57.         if(cross(p1, s[i], p2) < 0) {
  58.             while(up.size() >= 2 && cross(up[up.size() - 2], up[up.size() - 1], s[i]) >= 0)
  59.                 up.pop_back();
  60.             up.pb(s[i]);
  61.         }
  62.         else if(cross(p1, s[i], p2) > 0) {
  63.             while(down.size() >= 2 && cross(down[down.size() - 2], down[down.size() - 1], s[i]) <= 0)
  64.                 down.pop_back();
  65.             down.pb(s[i]);
  66.         }
  67.     }
  68.     while(up.size() > 2 && cross(up[up.size() - 2], up[up.size() - 1], p2) >= 0)
  69.         up.pop_back();
  70.     up.pb(p2);
  71.     while(down.size() > 2 && cross(down[down.size() - 2], down[down.size() - 1], p2) <= 0)
  72.         down.pop_back();
  73.     down.pb(p2);
  74.  
  75.     cout << down.size() + up.size() - 2 << endl;
  76.     if(n % 2 == 0) {
  77.        for(int i = up.size() - 1; i >= 0; --i)
  78.             cout << up[i].x << " " << up[i].y << endl;
  79.         for(int i = 1; i < down.size() - 1; ++i)
  80.             cout << down[i].x << " " << down[i].y << endl;
  81.         return 0;
  82.     }
  83.     else {
  84.         for(int i = 0; i < up.size(); ++i)
  85.             cout << up[i].x << " " << up[i].y << endl;;
  86.         for(int i = down.size() - 2; i >= 1; --i)
  87.             cout << down[i].x << " " << down[i].y << endl;
  88.         return 0;
  89.     }
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement