Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.04 KB | None | 0 0
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. class Point {
  9. public:
  10. long long x, y;
  11. Point(long long x, long long y) : x(x), y(y) {}
  12. Point() = default;
  13. friend istream& operator>>(istream& in, Point& p) {
  14. cin >> p.x >> p.y;
  15. return in;
  16. }
  17. };
  18.  
  19. class Vector {
  20. long long x, y;
  21. public:
  22. Vector() = default;
  23. Vector(long long x, long long y) : x(x), y(y) {}
  24. Vector(Point a, Point b) : x(b.x - a.x), y(b.y - a.y) {}
  25. Vector operator * (long long b) {
  26. return {x * b, y * b};
  27. }
  28. Vector operator / (long long b) {
  29. return {x / b, y / b};
  30. }
  31. Vector operator + (const Vector& o) {
  32. return {x + o.x, y + o.y};
  33. }
  34. friend long long operator^(const Vector& a, const Vector& b) {
  35. return a.x*b.y - a.y*b.x;
  36. }
  37. };
  38.  
  39. class Polygon {
  40. public:
  41. vector<Point> p;
  42. long long pnum;
  43. friend istream& operator>>(istream& in, Polygon& p) {
  44. cin >> p.pnum;
  45. for (int i = 0; i < p.pnum; ++i) {
  46. Point x;
  47. cin >> x;
  48. p.p.push_back(x);
  49. }
  50. return in;
  51. }
  52. void Sq() {
  53. long long sq = 0;
  54. Point strt(0, 0);
  55. for (int i = 0; i < pnum - 1; i++) {
  56. Vector p1(strt, p[i]);
  57. Vector p2(strt, p[i + 1]);
  58. sq += (p1 ^ p2);
  59. }
  60. Vector p1(strt, p[pnum - 1]);
  61. Vector p2(strt, p[0]);
  62. sq += (p1 ^ p2);
  63. if (sq % 2 == 1 || sq % 2 == -1) {
  64. cout << abs(sq / 2) << ".5";
  65. } else {
  66. cout << abs(sq / 2);
  67. }
  68. }
  69. };
  70.  
  71. bool q1(Point a, Point b) {
  72. return a.x < b.x || a.x == b.x && a.y < b.y;
  73. }
  74.  
  75. bool q2(Point a, Point b, Point c) {
  76. return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
  77. }
  78.  
  79. bool q3(Point a, Point b, Point c) {
  80. return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
  81. }
  82.  
  83. void obolo(vector<Point> &a) {
  84. if (a.size() == 1) return;
  85. sort(a.begin(), a.end(), &q1);
  86. Point p1 = a[0], p2 = a.back();
  87. vector<Point> up, down;
  88. up.push_back (p1);
  89. down.push_back (p1);
  90. for (size_t i=1; i<a.size(); ++i) {
  91. if (i==a.size()-1 || q2(p1, a[i], p2)) {
  92. while (up.size()>=2 && !q2(up[up.size() - 2], up[up.size() - 1], a[i]))
  93. up.pop_back();
  94. up.push_back (a[i]);
  95. }
  96. if (i==a.size()-1 || q3(p1, a[i], p2)) {
  97. while (down.size()>=2 && !q3(down[down.size() - 2], down[down.size() - 1], a[i]))
  98. down.pop_back();
  99. down.push_back (a[i]);
  100. }
  101. }
  102. a.clear();
  103. for (size_t i=0; i<up.size(); ++i)
  104. a.push_back (up[i]);
  105. for (size_t i=down.size()-2; i>0; --i)
  106. a.push_back (down[i]);
  107. }
  108.  
  109. int main() {
  110. cout.precision(15);
  111. Polygon p{};
  112. cin >> p;
  113. obolo(p.p);
  114. p.pnum = p.p.size();
  115. cout << p.pnum << endl;
  116. for (Point i: p.p) {
  117. Point x = i;
  118. cout << x.x << ' ' << x.y << endl;
  119. }
  120. p.Sq();
  121.  
  122.  
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement