解説中、多角形全体の面積を \(S\) とします。また、頂点 \(N+1\) を頂点 \(1\) 、頂点 \(N+2\) を頂点 \(2\) … と同一視します。

まず、 \(O(N^3)\) の解法を説明します。

• 全ての相異なる隣接しない頂点の組 \((p,q)\) について、以下を行う。
• 頂点 \(p,q\) を通る直線でピザを切り、頂点 \((p+1)\) を含む側を食べた場合の答えを求める。
  • この際、頂点 \((p+1)\) を含む側の面積を求める必要がある。
• この最小値が求めるべき答えである。

これは、以下のように \(O(N^2)\) まで改善できます。

• 全ての頂点 \(p\) について、以下を行う。
  • 頂点 \(q=(p+1), (p+2), \dots (p+N-2)\) に対して順に以下を行う。
    • 食べる部分に頂点 \(p,q,(q+1)\) からなる三角形を加える。これにより、現在食べる部分は、頂点 \(p,q\) を通る直線でピザを切り、頂点 \((p+1)\) を含む側を食べた時に一致する。

さらに、この解法は、以下のようなしゃくとり法で \(O(N)\) まで高速化できます。

• 頂点 \(q=2\) と初期化し、現状の食べる部分を空とする。
• 頂点 \(p=1,2,\dots,N\) について、以下を行う。
  • 現状の食べる部分の面積 \(E\) とする。
  • \(E < S/4\) である間、食べる部分に 頂点 \(p,q,(q+1)\) からなる三角形を追加し、 \(q\) に \(1\) 加算することを繰り返す。
  • その後、食べる部分から \(p,(p+1),q\) からなる三角形を削除する。

しゃくとり法の正当性について説明します。
\(p=i\) の処理が終わった時点で \(q=Q\) であったとします。このとき、 \(p>i\) について \(q<Q\) として最適値が得られることはありません。なぜなら、 \(p=i,q=Q-1\) とした時点で食べる部分の面積が \(E/4\) 未満であるのに、 \(p\) をこれ以上大きくして食べる部分を小さくしても、食べる部分の面積が \(p=i,q=Q-1\) とした場合よりも \(E/4\) に近づくということはないからです。

なお、以下の実装例では幾何ライブラリの実装として 競プロ典型 90 問 41問目 の 実装例 を利用しています。この実装だと凸包も簡単に実装でき、便利です。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

struct Point {
	long long px, py;
};

Point operator+(const Point& a1, const Point& a2) {
	return Point{ a1.px + a2.px, a1.py + a2.py };
}

Point operator-(const Point& a1, const Point& a2) {
	return Point{ a1.px - a2.px, a1.py - a2.py };
}

bool operator<(const Point& a1, const Point& a2) {
	if (a1.px < a2.px) return true;
	if (a1.px > a2.px) return false;
	if (a1.py < a2.py) return true;
	return false;
}

// 点 p1 と p2 の外積を求める
long long crs(Point p1, Point p2) {
	return p1.px * p2.py - p1.py * p2.px;
}

int main(){
  int n;
  cin >> n;
  vector<Point> pts(n);
  for(int i=0;i<n;i++){cin >> pts[i].px >> pts[i].py;}

  long long s=0;
  for(int i=2;i<n;i++){
    s+=abs(crs(pts[i-1]-pts[0],pts[i]-pts[0]));
  }

  long long res=8e18,e=0;
  int q=1;
  for(int p=0;p<n;p++){
    while(4*e<s){
      e+=abs(crs(pts[q]-pts[p],pts[(q+1)%n]-pts[p]));
      q++;q%=n;
      res=min(res,abs(4*e-s));
    }
    e-=abs(crs(pts[p]-pts[q],pts[(p+1)%n]-pts[q]));
    res=min(res,abs(4*e-s));
  }
  cout << res << '\n';
  return 0;
}