fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define x first.first
  3. #define y first.second
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<pair<ll,ll> ,ll> point;
  7. //checks if direction formed by abc is clockwise or anticlockwise
  8. ll cross (point a, point b, point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);}
  9. vector<point> ConvexHull(vector<point>&p, int n) {
  10.     int sz=0;
  11.     vector<point> hull(n+n);
  12.     sort(p.begin(), p.end());
  13.     for(int i = 0; i < n; ++i) {	//Computes lower hull of convex hull
  14.         while (sz > 1 and cross(hull[sz - 2], hull[sz - 1], p[i]) <= 0) --sz;
  15.         hull[sz++] = p[i];
  16.     }
  17.     for(int i = n - 2, j = sz + 1; i >= 0; --i) { //Appends upper hull
  18.         while (sz >= j and cross(hull[sz - 2], hull[sz - 1], p[i]) <= 0) --sz;
  19.         hull[sz++] = p[i];
  20.     } hull.resize(sz - 1);
  21.     return hull;
  22. }
  23. vector<point> inp,op;
  24. ll ans=0,u,v,w,n;
  25. int main() {
  26.     ios::sync_with_stdio(false);cin.tie(0);
  27.     cin>>n;
  28.     for (int i=0;i<n;i++) cin>>u>>v>>w,inp.push_back(make_pair(make_pair(u,v),w));
  29.     op=ConvexHull(inp,n);
  30.     for (int i=0;i<(int)op.size();i++) ans+=op[i].second;
  31.     cout<<ans;
  32. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
3
4 2 1
3 3 5
2 4 10
stdout
copy 
11
https://ideone.com/qOK4NY
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!