题解 P3454 【[POI2007]OSI-Axes of Symmetry】

Drinkwater · 2017-10-16 19:59:53 · 题解

NYG讲的神题，这一眼看上去像是计算几何的题目，但是巧妙地转换一下变成字符串处理会更好处理，我们把边和角（叉积）都hash下，然后跑一遍manacher，或者搞个反串跑个kmp，或者后缀数组，SAM什么的都可以，求个最长回文串，ok了，抢个沙发啊啊啊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
#define REP(i,a,b) for(register int i = (a),i##_end_ = (b); i <= i##_end_; ++i)
#define DREP(i,a,b) for(register int i = (a),i##_end_ = (b); i >= i##_end_; --i)
#define mem(a,b) memset(a,b,sizeof(a))
template<typename T> inline bool chkmin(T &a,const T &b) { return a > b ? a = b , 1 : 0;}
template<typename T> inline bool chkmax(T &a,const T &b) { return a < b ? a = b , 1 : 0;}
int read()
{
    register int f = 1,s = 0;char c = getchar();
    while(!isdigit(c)) { if(c == '-')f = -1;c = getchar();}
    while(isdigit(c)) { s = s * 10 + c - '0';c = getchar();}
    return f * s;
}
const int maxn = 100011;
int T,n;
typedef double db;
struct node
{
    int x,y;
}p[maxn];
int dis(int i,int j)
{
    db xa = p[i].x,ya = p[i].y,xb = p[j].x,yb = p[j].y;
    return (xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);
}
int cross(int i,int j,int k)
{
    node p1,p2;
    p1.x = p[j].x-p[i].x;p1.y = p[j].y-p[i].y;
    p2.x = p[k].x-p[i].x;p2.y = p[k].y-p[i].y;
    return p1.x*p2.y-p2.x*p1.y;
}
int s[maxn<<3];
int RL[maxn<<3],Maxr,pos;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    T = read();
    REP(I,1,T)
    {
        n = read();mem(s,0);mem(p,0);
        mem(RL,0);Maxr = pos = 0;
        REP(i,0,n-1)p[i].x = read(),p[i].y = read();
        REP(i,0,n-1)s[i<<1|1] = dis(i,(i+1)%n);
        REP(i,0,n-1)s[i<<1] = cross(i,(i-1+n)%n,(i+1)%n);
        //REP(i,0,(n<<1)-1)cout<<s[i]<<" ";puts(" ");
        int N = n<<1;
        REP(i,0,n-1)s[i+N] = s[i];
        int ans = 0;
        N<<=1;
        REP(i,0,N-1)
        {
            if(i < Maxr)RL[i] = min(RL[2*pos-i],Maxr-i);
            else RL[i] = 1;
            while(i - RL[i] >= 0 && i + RL[i] <= N && s[i+RL[i]] == s[i-RL[i]])RL[i]++;
            if(i+RL[i] > Maxr)Maxr = i+RL[i],pos = i;
            if(RL[i] >= n+1)ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}