Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pii pair<int,int>
- #define x first
- #define y second
- bool cross(pii a, pii o, pii b){
- return (o.x-a.x) * (b.y-o.y) >= (o.y-a.y) * (b.x-o.x);
- }
- int cac(pii a, pii o, pii b){
- return abs((o.x-a.x) * (b.y-o.y) - (o.y-a.y) * (b.x-o.x));
- }
- int main(){
- int n;
- pii dots[10000];
- cin >> n;
- for(int i = 0; i < n; ++i)cin >> dots[i].x >> dots[i].y;
- vector<pii> v;
- sort(dots, dots+n);
- for(int i = 0; i < n; ++i){
- while(v.size() >= 2 && cross(v[v.size()-2], v[v.size()-1], dots[i]))v.pop_back();
- v.emplace_back(dots[i]);
- }
- v.pop_back();
- int t = v.size();
- for(int i = n-1; i >= 0; --i){
- while(v.size() >= t+2 && cross(v[v.size()-2], v.back(), dots[i]))v.pop_back();
- v.emplace_back(dots[i]);
- }
- v.pop_back();
- double ans = 0;
- for(unsigned int i = 2; i < v.size(); ++i){
- ans += cac(v[0], v[i-1], v[i]);
- }
- cout << (int)(ans+1)/2 << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement