Advertisement
Guest User

Untitled

a guest
Nov 16th, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4.  
  5. struct point
  6. {
  7.     LL x;
  8.     LL y;
  9.     point () {}
  10.     point (LL x_, LL y_)
  11.     {
  12.         x = x_;
  13.         y = y_;
  14.     }
  15.     void show()
  16.     {
  17.         cout << "(" << x << "," << y << ")\n";
  18.     }
  19. };
  20.  
  21. struct vect
  22. {
  23.     LL x;
  24.     LL y;
  25.     vect () {}
  26.     vect (LL x_, LL y_)
  27.     {
  28.         x = x_;
  29.         y = y_;
  30.     }
  31.     vect (point A, point B)
  32.     {
  33.         x = A.x - B.x;
  34.         y = A.y - B.y;
  35.     }
  36.     void show()
  37.     {
  38.         cout << "(" << x << "," << y << ")\n";
  39.     }
  40. };
  41.  
  42. vector <point> Read()
  43. {
  44.     int n;
  45.     cin >> n;
  46.     vector <point> res(n);
  47.     for (int i=0; i!=n; ++i) cin >> res[i].x >> res[i].y;
  48.     return res;
  49. }
  50.  
  51. LL vectCross (vect V, vect U)
  52. {
  53.     return V.x * U.y - V.y * U.x;
  54. }
  55.  
  56. short det(point A, point B, point C)
  57. {
  58.     LL val = vectCross(vect(A,B), vect(A,C));
  59.     if (val == 0) return 0; //na linii
  60.     if (val > 0) return 1; //przeciwzegarowo
  61.     if (val < 0) return -1; //zegarowo
  62. }
  63. point X;
  64.  
  65. LL distSQ (point A, point B)
  66. {
  67.     return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
  68. }
  69.  
  70. bool polarCompare (const point &A, const point &B)
  71. {
  72.     short orient = det(X,A,B);
  73.     if (orient == 0) return distSQ(X,A) < distSQ(X,B);
  74.     return (orient == 1);
  75. }
  76.  
  77. void PolarSort(vector <point> &data)
  78. {
  79.     int ind = 0;
  80.     for (int i=0; i!=data.size(); i++)
  81.     {
  82.         if (data[i].y < data[ind].y) ind = i;
  83.         else if (data[i].x < data[ind].x && data[i].y == data[ind].y) ind = i;
  84.     }
  85.     X = data[ind];
  86.     swap(data[ind],data[0]);
  87.     sort(data.begin()+1, data.end(), polarCompare);
  88. }
  89.  
  90. bool FlatCmp (const point &A, const point &B)
  91. {
  92.     return (A.x < B.x || (A.x == B.x && A.y < B.y));
  93. }
  94.  
  95. void Graham (vector <point> &data)
  96. {
  97.     int n = data.size();
  98.     sort(data.begin(), data.end(), FlatCmp);
  99.  
  100.     vector <point> Top;
  101.     for (int i=0; i<n; ++i)
  102.     {
  103.         while (Top.size() > 1 && det(Top[Top.size()-2], Top[Top.size()-1], data[i]) != -1) Top.pop_back();
  104.         Top.push_back(data[i]);
  105.     }
  106.  
  107.     vector <point> Bottom;
  108.     for (int i=n-1; i>=0; --i)
  109.     {
  110.         while (Bottom.size() > 1 && det(Bottom[Bottom.size()-2], Bottom[Bottom.size()-1], data[i]) != -1) Bottom.pop_back();
  111.         Bottom.push_back(data[i]);
  112.     }
  113.  
  114.     data = Top;
  115.     for (int i=1; i<Bottom.size()-1; ++i) data.push_back(Bottom[i]);
  116. }
  117.  
  118. void CalcArea (vector <point> &K)
  119. {
  120.     LL res = 0;
  121.     int j = K.size() - 1;
  122.     for (int i=0; i<K.size(); ++i)
  123.     {
  124.         res += K[i].x * K[j].y;
  125.         res -= K[i].y * K[j].x;
  126.         j = i;
  127.     }
  128.  
  129.     cout << (res >> 1);
  130.     if (res%2) cout << ".500000";
  131.     else cout << ".000000";
  132.  
  133. }
  134.  
  135. int main()
  136. {
  137.     ios_base::sync_with_stdio(0);
  138.     cin.tie(0);
  139.     cout.tie(0);
  140.  
  141.     vector <point> All = Read();
  142.     Graham(All);
  143.     CalcArea(All);
  144.     return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement