题解

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 210
#define INF 0x3FFFFFFF

int opt[MAXN];
int psum[MAXN];
int canon[MAXN*2][MAXN*2];
vector<int> lparents[MAXN][MAXN];
vector<int> rparents[MAXN][MAXN];

int dp[MAXN][MAXN][MAXN][2];

int main() {
  int N; cin >> N;
  vector<pair<long long, long long> > A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
  }
  vector<int> S(1, 0);
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    int k = (i + 2) % N;
    S.push_back(abs(A[i].first - A[j].first) +
                abs(A[i].second - A[j].second));
    if ((A[i].first - A[j].first) * (A[k].second - A[j].second) -
        (A[k].first - A[j].first) * (A[i].second - A[j].second) > 0) {
      S.push_back(-1);
    } else {
      S.push_back(-2);
    }
  }
  S.back() = 0;
  for (int i = 0; i < N; i++) {
    psum[i + 1] = opt[i + 1] = opt[i] + S[2 * i + 1];
  }
  opt[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    opt[i] = min(opt[i], opt[i + 1] + S[2 * i + 1]);
  }
  for (int ln = 1; ln <= S.size(); ln++) {
    for (int i = 0; i + ln <= S.size(); i++) {
      for (int& j = canon[i][ln]; j < i; j++) {
        if (canon[j][ln - 1] == canon[i][ln - 1] &&
            S[j + ln - 1] == S[i + ln - 1]) {
          break;
        }
      }
    }
  }
  for (int i = 0; i < S.size(); i += 2) {
    for (int ln = 3; i + ln <= S.size(); ln += 2) {
      if (i != canon[i][ln]) {
        continue;
      }
      lparents[canon[i + 2][ln - 2] / 2][ln / 2].push_back(i / 2);
      rparents[canon[i][ln - 2] / 2][ln / 2].push_back(i / 2);
    }
  }

  int result = 0;
  for (int ln = N; ln >= 1; ln--) {
    for (int i = 0; i + ln <= N + 1; i++) {
      if (canon[2 * i][2 * ln - 1] != 2 * i) {
        continue;
      }

      int dist_across = psum[i + ln - 1] - psum[i];
      for (int strt = 0; strt < ln; strt++) {
        for (int side = 0; side < 2; side++) {
          if (i == 0 || i + ln == N + 1) {
            dp[i][ln][strt][side] = -opt[i + strt];
            continue;
          }
          int lft_cst = -INF;
          for (int j : lparents[i][ln]) {
            lft_cst = max(lft_cst, S[2 * j + 1] + dp[j][ln + 1][strt + 1][0]);
          }

          int rht_cst = -INF;
          for (int j : rparents[i][ln]) {
            rht_cst = max(rht_cst,
                          S[2 * (j + ln) - 1] + dp[j][ln + 1][strt][1]);
          }
          (side ? lft_cst : rht_cst) += dist_across;
          dp[i][ln][strt][side] = min(lft_cst, rht_cst);
          if (ln == 1) {
            result = max(result, dp[i][ln][strt][side]);
          }
        }
      }
    }
  }
  cout << result << endl;
  
  return 0;
}