SHARE
TWEET

Untitled

a guest Apr 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top