Rockdu's Blog

2
12
1 -1
2 -1
2 1
1 1
1 2
-1 2
-1 1
-2 1
-2 -1
-1 -1
-1 -2
1 -2
6
-1 1
-2 0
-1 -1
1 -1
2 0
1 1

4
2​​

讲讲这道题的心路历程吧：

这道题虽然有个明显的O(n^2)算法对吧，但是明摆着要O(n)。

于是就开始各种乱搞了……

乱搞1：把边考虑上，取每个边的中点和所有的多边形顶点，求出所有点的平均点(横纵坐标取平均值)，因为图形要对称两边的点一定要相等。那么可以O(n)枚举对角线验证过不过平均点。不过这个算法一经提出就被自己卡了：

于是就有了乱搞2：我们再判一下一个点向左向右发出的两条边是不是对称。然后我又把自己卡了：

真是个悲惨的故事！不过这个思维是可以无限延伸的，我们可以一直往两边判断，实际上也就乘个常数，说不准就卡过了呢！

下面我们说说正解吧：

先是三个字正解：

字符串

这是一道字符串……

什么，为什么我想了半天都没看出来这是道字符串？？？

对呀……我太菜了……

我们考虑把多边形哈希，不过我们哈希的姿势要独特一些：沿用乱搞1，我们把边和角都提出来哈希，边用边长，角就用两条边的向量在模意义下的叉积。这样我们保证了无论图形怎么摆，只要边角哈希值的有序序列一样两个图形就一样。那么要两边对称变成了什么呢？

——回文串

是的，然后就变成了求环上的长度为n * 2 + 1的回文串个数……这道题没了。

我的字符串修为太低了……

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define sqr(x) (1ll * (x) * (x))
using namespace std;
const int maxn = 1e6 + 5, base = 19260817, P = 1e9 + 7;
int t, n, x[maxn], y[maxn], ag[maxn], grp[maxn << 1], len;

int GetAng(int x1, int y1, int x2, int y2) {
    return ((long long)abs(1ll * x1 * y2 - 1ll * y1 * x2) % P + P) % P;
}

int RL[maxn], ans;
void Manacher(int * s, int len) {
    int Mid = 1, Mr = 1, l, r;
    for(register int i = 1; i <= len; ++i) {
        RL[i] = min(RL[(Mid << 1) - i], Mr - i);
        for(;(l = i - RL[i]) >= 1 && (r = i + RL[i]) <= len; ++RL[i]) {
            if(s[l] != s[r]) {++RL[i]; break;}
        }
        --RL[i];
        if(i + RL[i] > Mr) Mr = i + RL[i], Mid = i;
    }
}

int ch[maxn << 2], cnt;

int main() {
    scanf("%d", &t);
    while(t--) {
        cnt = ch[0] = grp[0] = len = ans = 0;
        scanf("%d", &n);
        for(register int i = 1; i <= n; ++i)
            scanf("%d%d", &x[i], &y[i]);
        x[0] = x[n], y[0] = y[n];
        x[n + 1] = x[1], y[n + 1] = y[1];
        for(register int i = 1; i <= n; ++i)
            ag[i] = GetAng(x[i - 1] - x[i], y[i - 1] - y[i], x[i + 1] - x[i], y[i + 1] - y[i]);
        for(register int i = 1; i <= n; ++i) {
            grp[++grp[0]] = ag[i];
            grp[++grp[0]] = (sqr(x[i + 1] - x[i]) % P + sqr(y[i + 1] - y[i]) % P) % P;
        }
        for(register int i = 1; i <= grp[0]; ++i) {
            grp[i + grp[0]] = grp[i];
        }
        
        grp[0] <<= 1, len = n * 2;
        ch[++cnt] = -1;
        for(register int i = 1; i <= grp[0]; ++i)
            ch[++cnt] = grp[i], ch[++cnt] = -1;
        
        Manacher(ch, cnt);
        for(register int i = 1; i <= cnt; ++i)
            if(RL[i] / 2 >= n) 
                ++ans;
        printf("%d\n", ans / 2);
    }
    return 0;
}