ccbeginner

TIOJ 1280

Nov 3rd, 2020
632
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int,int>
  4. #define x first
  5. #define y second
  6.  
  7. bool cross(pii a, pii o, pii b){
  8.     return (o.x-a.x) * (b.y-o.y) >= (o.y-a.y) * (b.x-o.x);
  9. }
  10.  
  11. int cac(pii a, pii o, pii b){
  12.     return abs((o.x-a.x) * (b.y-o.y) - (o.y-a.y) * (b.x-o.x));
  13. }
  14.  
  15. int main(){
  16.     int n;
  17.     pii dots[10000];
  18.     cin >> n;
  19.     for(int i = 0; i < n; ++i)cin >> dots[i].x >> dots[i].y;
  20.     vector<pii> v;
  21.     sort(dots, dots+n);
  22.     for(int i = 0; i < n; ++i){
  23.         while(v.size() >= 2 && cross(v[v.size()-2], v[v.size()-1], dots[i]))v.pop_back();
  24.         v.emplace_back(dots[i]);
  25.     }
  26.     v.pop_back();
  27.     int t = v.size();
  28.     for(int i = n-1; i >= 0; --i){
  29.         while(v.size() >= t+2 && cross(v[v.size()-2], v.back(), dots[i]))v.pop_back();
  30.         v.emplace_back(dots[i]);
  31.     }
  32.     v.pop_back();
  33.     double ans = 0;
  34.     for(unsigned int i = 2; i < v.size(); ++i){
  35.         ans += cac(v[0], v[i-1], v[i]);
  36.     }
  37.     cout << (int)(ans+1)/2 << '\n';
  38.     return 0;
  39. }
RAW Paste Data