AlexNeagu11

InfasuratoareOptim

Mar 19th, 2022
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. ifstream in("infasuratoare.in");
  5. ofstream out("infasuratoare.out");
  6. struct point {
  7. int x, y;
  8. void read() {
  9. cin >> x >> y;
  10. }
  11. void write() {
  12. cout << x << ' ' << y << '\n';
  13. }
  14. point operator - (const point &B) const {
  15. return point{x - B.x, y - B.y};
  16. }
  17. void operator -= (const point &B) {
  18. x -= B.x;
  19. y -= B.y;
  20. }
  21. int operator * (const point &B) const {
  22. return x * B.y - y * B.x;
  23. }
  24. int orientation(const point &A, const point &B) const {
  25. return (A - *this) * (B - *this);
  26. }
  27. int dist(point A) {
  28. A -= *this;
  29. return A.x * A.x + A.y * A.y;
  30. }
  31. bool operator <(const point &A) {
  32. if(x == A.x) {
  33. return y < A.y;
  34. }
  35. return x < A.x;
  36. }
  37.  
  38. };
  39. vector<point> upperHull, lowerHull;
  40.  
  41. void add(bool upper, vector<point> &hull, point p) {
  42. while(hull.size() >= 2) {
  43. int sz = hull.size();
  44. point P1 = hull[sz - 2];
  45. point P2 = hull[sz - 1];
  46. int dir = P1.orientation(P2, p);
  47. if(dir == 0 || (dir < 0) == upper ) {
  48. break;
  49. }
  50. hull.pop_back();
  51. }
  52. hull.push_back(p);
  53. }
  54.  
  55. int32_t main() {
  56.  
  57. int n;
  58. cin >> n;
  59. vector<point> points(n);
  60. for(int i = 0; i < n; ++i) {
  61. points[i].read();
  62. }
  63.  
  64. sort(points.begin(), points.end());
  65. for(int i = 0; i < n; ++i) {
  66. add(true, upperHull, points[i]);
  67. add(false, lowerHull, points[i]);
  68. }
  69.  
  70. upperHull.pop_back();
  71. lowerHull.erase(lowerHull.begin());
  72. reverse(lowerHull.begin(), lowerHull.end());
  73. cout << upperHull.size() + lowerHull.size() << '\n';
  74.  
  75. for(auto it : upperHull) {
  76. it.write();
  77. }
  78. for(auto it : lowerHull) {
  79. it.write();
  80. }
  81.  
  82. }
Advertisement
Add Comment
Please, Sign In to add comment