fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. struct point {
  5.     int x,y;
  6.     bool operator <(const point other) const {
  7.         if(other.x!=x) return x<other.x;
  8.         return y<other.y;
  9.     }
  10.     friend int cross(point a, point b) {return a.x*b.y-a.y*b.x;}
  11. };
  12. int32_t main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(0), cout.tie(0);
  15.     int n; cin >> n;
  16.     vector <point> p(2*n+1);
  17.     int pref[2*n+1];
  18.     pref[1]=0;
  19.     for(int i=1;i<=n;i++) cin >> p[i].x >> p[i].y, p[i+n]=p[i];
  20.     for(int i=2;i<=2*n;i++) pref[i]=pref[i-1]+cross(p[i-1],p[i]);
  21.     int area=pref[n+1],ans=LLONG_MAX;
  22.     for(int p1=1,p2=3;p1<=n;p1++) {
  23.         p2=max(p2,p1+2);
  24.         int ma=0;
  25.         if(p2>p1+2) p2--;
  26.         while(true) {
  27.             int S=abs(pref[p2]-pref[p1]+cross(p[p2],p[p1]));
  28.             int d=min(S,area-S);
  29.             ma=max(ma,d);
  30.             if(2*S>=area) break;
  31.             p2++;
  32.         }
  33.         ans=min(ans,ma);
  34.     }
  35.     cout << area-ans << ' ' << ans;
  36.     return 0;
  37. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
0 0
3 0
3 1
2 2
0 1
stdout
copy 
7 2
https://ideone.com/9RDidZ
language:
C++ (gcc 8.3)
created:
25 days ago
visibility:
public

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!