fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 205;
  4. const int mod = 1e9 + 7;
  5. const int shift = 1337;
  6. const int pp = 10007;
  7.  
  8. int n, x[maxn], y[maxn];
  9. int a[maxn], h[maxn][maxn], sum[maxn][maxn];
  10. int l[maxn], dp[maxn][maxn][maxn][2];
  11.  
  12. bool side(int x1, int y1, int x2, int y2, int x3, int y3) {
  13.     long long ux = x2 - x1;
  14.     long long uy = y2 - y1;
  15.     long long vx = x3 - x1;
  16.     long long vy = y3 - y1;
  17.     return ux * vy - uy * vx < 0;
  18. }
  19.  
  20. int go(int b, int e, int d, bool s) {
  21.     if (dp[b][e][d][s] >= 0) {
  22.         return dp[b][e][d][s];
  23.     } else if (b == 0 || e == 0) {
  24.         return -l[b + d];
  25.     }
  26.     int left = -1e9, right = -1e9;
  27.     for (int i = 1; i + e - b < n; i++) {
  28.     	int l = i, r = i + e - b;
  29.     	if (h[b][e] == h[l][r]) {
  30.     		int lcost = go(l - 1, r, d + 1, 0);
  31.     		int rcost = go(l, (r + 1) % n, d, 1);
  32.     		if (!s) {
  33.     			lcost += a[2 * l - 1];
  34.     			rcost += sum[l][(r + 1) % n];
  35.     		} else {
  36.     			lcost += sum[l - 1][r];
  37.     			rcost += a[2 * r + 1];
  38.     		}
  39.     		left = max(lcost, left);
  40.     		right = max(rcost, right);
  41.     	}
  42.     }
  43.     int ret = min(left, right);
  44.     for (int i = 1; i + e - b < n; i++) {
  45.     	int l = i, r = i + e - b;
  46.     	if (h[b][e] == h[l][r]) {
  47.     		dp[l][r][d][s] = ret;
  48.     	}
  49.     }
  50. 	return ret;
  51. }
  52.  
  53. int main() {
  54.     //freopen("lightsout.in", "r", stdin);
  55.     //freopen("lightsout.out", "w", stdout);
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);
  58.     cin >> n;
  59.     for (int i = 0; i < n; i++) {
  60.         cin >> x[i] >> y[i];
  61.     }
  62.     for (int i = 0; i < n; i++) {
  63.         a[2 * i] = side(x[(i + n - 1) % n], y[(i + n - 1) % n],
  64.                         x[i], y[i],
  65.                         x[(i + 1) % n], y[(i + 1) % n]);
  66.         --a[2 * i];
  67.         a[2 * i + 1] = abs(x[i] - x[(i + 1) % n])
  68.         + abs(y[i] - y[(i + 1) % n]);
  69.     }
  70.     a[0] = -2; //distinct start
  71.     for (int b = 0; b < n; b++) {
  72.         for (int e = 0; e < n; e++) {
  73.             for (int i = 2 * b; ; i = (i + 1) % (2 * n)) {
  74.                 h[b][e] = (1LL * h[b][e] * pp + a[i] + shift) % mod;
  75.                 if (a[i] > 0) {
  76.                     sum[b][e] += a[i];
  77.                 }
  78.                 if (i == 2 * e) {
  79.                     break;
  80.                 }
  81.             }
  82.         }
  83.     }
  84.     for (int i = 0; i < n; i++) {
  85.     	l[i] = min(sum[0][i], sum[i][0]);
  86.     }
  87.     fill_n(&dp[0][0][0][0], maxn * maxn * maxn * 2, -1);
  88.     int res = 0;
  89.     for (int i = 0; i < n; i++) {
  90.     	if (a[i] == -1) {
  91.     		res = max(go(i, i, 0, 0), res);
  92.     		break;
  93.     	}
  94.     }
  95.     for (int i = 0; i < n; i++) {
  96.     	if (a[i] == 0) {
  97.     		res = max(go(i, i, 0, 0), res);
  98.     		break;
  99.     	}
  100.     }
  101.     cout << res << '\n';
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.06s 71104KB
comments (?)
stdin 
4
0 0
0 10
1 10
1 0
stdout 
2
https://ideone.com/tnQIzM
language:
C++14 (gcc 8.3)
created:
8 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!