fork download
  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
stdin
5
0 0
3 0
3 1
2 2
0 1
stdout
7 2