Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- struct point
- {
- LL x;
- LL y;
- point () {}
- point (LL x_, LL y_)
- {
- x = x_;
- y = y_;
- }
- void show()
- {
- cout << "(" << x << "," << y << ")\n";
- }
- };
- struct vect
- {
- LL x;
- LL y;
- vect () {}
- vect (LL x_, LL y_)
- {
- x = x_;
- y = y_;
- }
- vect (point A, point B)
- {
- x = A.x - B.x;
- y = A.y - B.y;
- }
- void show()
- {
- cout << "(" << x << "," << y << ")\n";
- }
- };
- vector <point> Read()
- {
- int n;
- cin >> n;
- vector <point> res(n);
- for (int i=0; i!=n; ++i) cin >> res[i].x >> res[i].y;
- return res;
- }
- LL vectCross (vect V, vect U)
- {
- return V.x * U.y - V.y * U.x;
- }
- short det(point A, point B, point C)
- {
- LL val = vectCross(vect(A,B), vect(A,C));
- if (val == 0) return 0; //na linii
- if (val > 0) return 1; //przeciwzegarowo
- if (val < 0) return -1; //zegarowo
- }
- point X;
- LL distSQ (point A, point B)
- {
- return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
- }
- bool polarCompare (const point &A, const point &B)
- {
- short orient = det(X,A,B);
- if (orient == 0) return distSQ(X,A) < distSQ(X,B);
- return (orient == 1);
- }
- void PolarSort(vector <point> &data)
- {
- int ind = 0;
- for (int i=0; i!=data.size(); i++)
- {
- if (data[i].y < data[ind].y) ind = i;
- else if (data[i].x < data[ind].x && data[i].y == data[ind].y) ind = i;
- }
- X = data[ind];
- swap(data[ind],data[0]);
- sort(data.begin()+1, data.end(), polarCompare);
- }
- bool FlatCmp (const point &A, const point &B)
- {
- return (A.x < B.x || (A.x == B.x && A.y < B.y));
- }
- void Graham (vector <point> &data)
- {
- int n = data.size();
- sort(data.begin(), data.end(), FlatCmp);
- vector <point> Top;
- for (int i=0; i<n; ++i)
- {
- while (Top.size() > 1 && det(Top[Top.size()-2], Top[Top.size()-1], data[i]) != -1) Top.pop_back();
- Top.push_back(data[i]);
- }
- vector <point> Bottom;
- for (int i=n-1; i>=0; --i)
- {
- while (Bottom.size() > 1 && det(Bottom[Bottom.size()-2], Bottom[Bottom.size()-1], data[i]) != -1) Bottom.pop_back();
- Bottom.push_back(data[i]);
- }
- data = Top;
- for (int i=1; i<Bottom.size()-1; ++i) data.push_back(Bottom[i]);
- }
- void CalcArea (vector <point> &K)
- {
- LL res = 0;
- int j = K.size() - 1;
- for (int i=0; i<K.size(); ++i)
- {
- res += K[i].x * K[j].y;
- res -= K[i].y * K[j].x;
- j = i;
- }
- cout << (res >> 1);
- if (res%2) cout << ".500000";
- else cout << ".000000";
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- vector <point> All = Read();
- Graham(All);
- CalcArea(All);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement