【bzoj1100】[POI2007]对称轴osi

2015.07.11 16:30 Sat | 43次阅读 | 旧日oi | 固定链接 | 源码

Description

给定一个多边形,求有多少条对称轴,边数10^5

题解

多边形的对称轴要么过边的中点,要么过顶点,并且对称轴两侧的边和角呈回文状,所以我们可以想到manacher算法。把边和角作为元素存起来,复制一遍然后跑manacher。
细节:
1.把边拆成两段相等的存,中间加一个0,这样过边的对称轴也能算。
2.计算角的时候注意用叉积判断凸还是凹的,否则第一个测试点过不去。
3.仅有一个位置可能被算了两次(就是第一个串的中点,然后复制之后又被算了一次),解决办法是复制的时候不复制最后一个点。
4.每条对称轴被算了两次,答案/2;
5.知道了第4条没注意到第3条也能过。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 1000005
int T,n,cnt;
const double pi=acos(-1);
struct Point{
    double x,y;
    Point(double _=0,double __=0):x(_),y(__){}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    Point operator *(double a)const{    
        return Point(x*a,y*a);
    }
}p[N];
double a[N];
int l[N];
#define eps 1e-12
double dis(Point p)
{
    return p.x*p.x+p.y*p.y;
}
double get_alp(Point a,Point b,Point c)
{
    return acos((dis(a)+dis(b)-dis(c))/(2*sqrt(dis(a)*dis(b))));
}
double cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
int main()
{
    freopen("CC.in","r",stdin);
    freopen("CC.out","w",stdout);
    int i,j,ans;a[0]=-0x3f3f3f3f;
    for(cin>>T;T;T--)
    {
        cin>>n;cnt=ans=0;
        memset(l,0,sizeof(l));
        for(i=1;i<=n;i++) 
            scanf("%lf%lf",&p[i].x,&p[i].y);
        p[n+1]=p[1];p[0]=p[n];
        for(i=1;i<=n;i++) 
        {
            a[++cnt]=get_alp(p[i]-p[i-1],p[i+1]-p[i],p[i+1]-p[i-1]);
            if(cross(p[i]-p[i-1],p[i+1]-p[i-1])>0) a[cnt]=2*pi-a[cnt];
            a[++cnt]=dis(p[i+1]-p[i]);
            a[++cnt]=0;
            a[++cnt]=dis(p[i+1]-p[i]);
        }
        for(i=1;i<=cnt;i++) a[cnt+i]=a[i];
        cnt<<=1;
        //a[cnt]=0x3f3f3f3f;加不加无所谓,反正多的那个1会被下取整 
        int mx=0,id=0;
        for(i=1;i<=cnt;i++)
        {
            if(mx>i) l[i]=min(l[2*id-i],mx-i);
            else l[i]=1;
            for(;fabs(a[i-l[i]]-a[i+l[i]])<eps;l[i]++);
            if((l[i]-1)*2>=(cnt>>1)) 
            ans++;
            if(l[i]+i>mx) id=i,mx=l[i]+i;
        }
        cout<<ans/2<<endl;
    }
    return 0;
}```