Lights Out

可以把多边形转换成字符串，让Bessie在字符串上走路，问题就会好解。字符串构造的办法，就是一个字符代表当前点的角度（90度，或者270度），一个字符代表下一段路的长度。这样走len步，就得到长度为2len+1的子串，包括len+1个“角度字符”，和len个中间的“长度字符”。

在字符串上找最短的不重复出现的子串，可以用哈希+map。

要判断三个点组成的角的角度，通用办法是使用叉积，这个知识点比较常见，需要掌握。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
pi vs[205];
int s[405];     // interior angle, length of edge * 10, interior angle, ...
int dist[205];  // distance from exit (clockwise)
int total;      // total distance
map<int,int> m; // hash -> count
int h[405], p[405];
const int A = 911382323, M = 972663749;
 
int angle(pi p0, pi p1, pi p2) {
    int crossprod = (p1.first-p0.first)*(p2.second-p1.second) - (p1.second-p0.second)*(p2.first-p0.first);
    return crossprod < 0 ? 1 : 2;   // 1 - 90, 2 - 270
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &vs[i].first, &vs[i].second);
    for (int i = 0; i < n; i++) {
        int prv = (i+n-1) % n, nxt = (i+1) % n;
        int a = angle(vs[prv], vs[i], vs[nxt]);
        int d = abs(vs[i].first - vs[nxt].first) + abs(vs[i].second - vs[nxt].second);
        s[i*2] = a;             // compose string for searching
        s[i*2+1] = d * 10;
        if (i) 
            dist[i] = dist[i-1] + (abs(vs[i].first-vs[i-1].first) + abs(vs[i].second-vs[i-1].second));
    }
    total = dist[n-1] + abs(vs[n-1].first-vs[0].first) + abs(vs[n-1].second-vs[0].second);
 
    p[0] = 1; h[0] = s[0]; 
    for (int i = 1; i < 2*n; i++) {
        p[i] = (ll)p[i-1] * A % M;
        h[i] = ((ll)h[i-1] * A + s[i]) % M;
    }
    auto hsh = [](int a, int b) -> int {
        int res;
        if (a == 0) res = h[b];
        else res = (h[b] - (ll)h[a-1] * p[b-a+1] + (ll)h[a-1] * M) % M;
        return res;
    };
    for (int i = 2; i < 2*n; i+=2)
        for (int j = i; j < 2*n; j+=2)
            m[hsh(i,j)]++;
 
    int ans = 0;
    for (int i = 2; i < 2*n; i+=2)     // start from non-exit
        for (int j = i; j < 2*n; j+=2)
            if (m[hsh(i,j)] == 1) {
                int actual = dist[j/2] - dist[i/2] + min(dist[j/2], total-dist[j/2]);
                int best = min(dist[i/2], total-dist[i/2]);
                ans = max(ans, actual-best);
                break;
            }
    printf("%d", ans);
    return 0;
}