Luogu

BZOJ

分析

把每条边的长度和每个角的大小按顺序排列,可以组成一个环。

把这个环在某条对称轴的地方断开,形成的串显然是回文的。

于是把这个环倍长,然后长度 $> len$ 的回文串个数就是答案(这里的 $len$ 是环长)。直接跑 $\mathrm{manacher}$ 即可。

具体的,长度可以不开根号,角的大小可以用叉积。然后最后的答案要 $/2$ ,因为每条对称轴被算了两次。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

struct Point { int x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
inline int sqr(int x) { return x*x; }
inline int dis(Point a,Point b) { return sqr(a.x-b.x)+sqr(a.y-b.y); }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,s[N],f[N];
Point p[N];

int main() {
    int T=read();
    while (T--) {
        n=read();
        for (re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
        
        for (re int i=1;i<=n;++i)
            s[i*2-1]=dis(p[i],p[i%n+1]);
        for (re int i=1;i<=n;++i)
            s[i*2-2]=cross(p[(i-2+n)%n+1]-p[i],p[i%n+1]-p[i]);
        for (re int i=0;i<n*2;++i) s[i+n*2]=s[i];
        
        int mid,Maxright=0;
        for (re int i=0;i<n*4;++i) {
            if (i<Maxright) f[i]=min(f[mid*2-i],f[mid]+mid-i);
            else f[i]=1;
            for (;s[i+f[i]]==s[i-f[i]];++f[i])
                if (f[i]+i>Maxright) Maxright=i+f[i],mid=i;
        }
        
        int ans=0;
        for (re int i=0;i<n*4;++i) ans+=(f[i]>n);
        printf("%d\n",ans>>1);
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 36 PM