Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef struct point {
  6. long long x, y;
  7.  
  8. point() {}
  9.  
  10. point(long long x, long long y) : x(x), y(y) {}
  11. };
  12.  
  13. point operator+(point p1, point p2) {
  14. return point(p1.x + p2.x, p1.y + p2.y);
  15. }
  16.  
  17. point operator-(point p1) {
  18. return point(-p1.x, -p1.y);
  19. }
  20.  
  21. point operator-(point p1, point p2) {
  22. return p1 + (-p2);
  23. }
  24.  
  25. long long dot(point p1, point p2) {
  26. return p1.x * p2.x + p1.y * p2.y;
  27. }
  28.  
  29. long long cross(point p1, point p2) {
  30. return p1.x * p2.y - p1.y * p2.x;
  31. }
  32.  
  33. bool cmp(point &a, point &b) {
  34. if (a.x != b.x)
  35. return a.x < b.x;
  36. return a.y < b.y;
  37. }
  38.  
  39. void build_convex_hull(vector<point> &pst, vector<point> &ch) {
  40. vector<point> lower_hull, upper_hull;
  41. lower_hull.push_back(pst[0]);
  42. upper_hull.push_back(pst[0]);
  43. long double k = (long double)(pst.back().y - pst[0].y) / (pst.back().x - pst[0].x), m = pst[0].y - pst[0].x * k;
  44. for (int i = 1; i < pst.size(); i++) {
  45. if (pst[i].y > k * pst[i].x + m || i == pst.size() - 1) {
  46. while (upper_hull.size() > 1 && cross(pst[i] - upper_hull[upper_hull.size() - 2], upper_hull.back() - upper_hull[upper_hull.size() - 2]) <= 0)
  47. upper_hull.pop_back();
  48. upper_hull.push_back(pst[i]);
  49. }
  50. if (pst[i].y < k * pst[i].x + m || i == pst.size() - 1) {
  51. while (lower_hull.size() > 1 && cross(pst[i] - lower_hull[lower_hull.size() - 2], lower_hull.back() - lower_hull[lower_hull.size() - 2]) >= 0)
  52. lower_hull.pop_back();
  53. lower_hull.push_back(pst[i]);
  54. }
  55. }
  56. for (int i = 0; i < upper_hull.size(); i++)
  57. ch.push_back(upper_hull[i]);
  58. for (int i = lower_hull.size() - 2; i >= 1 ; i--)
  59. ch.push_back(lower_hull[i]);
  60. }
  61.  
  62. long double get_polygon_area(vector<point> &polygon) {
  63. long long ar = 0;
  64. for (int i = 0; i < polygon.size() - 1; i++)
  65. ar += cross(polygon[i], polygon[i + 1]);
  66. ar += cross(polygon.back(), polygon[0]);
  67. return abs(ar) / 2.;
  68. }
  69.  
  70. int main() {
  71. //freopen("hull.in", "r", stdin);
  72. //freopen("hull.out", "w", stdout);
  73. int n;
  74. long long s;
  75. cin >> n;//>> s;
  76. vector<point> pts(n);
  77. long long j = 0;
  78. for (int i = 0; i < n; i++) {
  79. //pts[i] = point(i, i * i);
  80. cin >> pts[i].x >> pts[i].y;
  81. }
  82. vector<point> nvc;
  83. sort(pts.begin(), pts.end(), cmp);
  84. nvc.push_back(pts[0]);
  85. for (int i = 1; i < pts.size(); i++)
  86. if (pts[i].x != pts[i - 1].x || pts[i].y != pts[i - 1].y)
  87. nvc.push_back(pts[i]);
  88. pts = nvc;
  89. if (nvc.size() == 1) {
  90. cout << "1\n" << nvc[0].x << ' ' << nvc[0].y << "\n0";
  91. return 0;
  92. }
  93. if (pts[0].x == pts.back().x) {
  94. cout << "2\n" << pts[0].x << ' ' << pts[0].y << '\n';
  95. cout << pts.back().x << ' ' << pts.back().y << "\n0";
  96. return 0;
  97. }
  98. vector<point> convex_hull;
  99. build_convex_hull(pts, convex_hull);
  100. //cout << convex_hull.size() << '\n';
  101. //for (int i = 0; i < convex_hull.size(); i++)
  102. // cout << convex_hull[i].x << ' ' << convex_hull[i].y << '\n';
  103. long double gg = 0;
  104. for (int i = 1; i < convex_hull.size(); i++)
  105. gg += sqrt((convex_hull[i].x - convex_hull[i - 1].x) * (convex_hull[i].x - convex_hull[i - 1].x) + (convex_hull[i].y - convex_hull[i - 1].y) * (convex_hull[i].y - convex_hull[i - 1].y));
  106. gg += sqrt((convex_hull[0].x - convex_hull.back().x) * (convex_hull[0].x - convex_hull.back().x) + (convex_hull[0].y - convex_hull.back().y) * (convex_hull[0].y - convex_hull.back().y));
  107. cout << setprecision(20) << gg << '\n' << get_polygon_area(convex_hull) << '\n';
  108. return 0;
  109. }
  110. /*
  111. 4499550010000
  112. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement