「题解」对称的多边形

(未完待续)

题目链接:Quest Online Judge 2027

题目

题目描述

给你一个多边形,求它对称轴的个数。

数据范围

百分比变量数据范围
$15\%$$n$$1\leq n\leq 15$
$100\%$$T$$1\leq T\leq 10$
$n$$3\leq n\leq 10^5$
$x,y$$-10^8\leq n\leq 10^8$

时空限制

题目编号时间限制空间限制
Quest Online Judge 2027$1\text{s}$$256\text{MiB}$

题解

解法 A(暴力)

思路

假设所有的图形都是不交叉多边形(所有凸多边形和部分的凹多边形),则可枚举求解。

枚举每一个点及其对点(或对点的中点)和每一条边,判断是否是对称轴:

  • 对称轴左右的对应点的连线应当被对称轴垂直平分。

这一点我们可以快速地用向量解决,因为。

$$\huge{\vec{a}\cdot\vec{b}=0\Leftrightarrow\vec{a}\perp\vec{b}}$$

算法的渐近时间复杂度为 $\Theta(n^2)$ ,期望得分为 $15\to 100$ 分,实际得分 $77$ 分。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;

const int MAXN=100000+5;

int T;

inline void Read(void);
inline void Work(void);

int main(void){
    scanf("%d",&T);
    while(T--){
        Read();
        Work();
    }
    return 0;
}

struct Node{
    double x,y;
    inline Node(void){
        x=y=0;
        return;
    }
    inline Node(reg double a,reg double b){
        x=a,y=b;
        return;
    }
    inline void Read(void){
        scanf("%lf%lf",&x,&y);
        return;
    }
};

int n;
Node a[MAXN];

inline void Read(void){
    scanf("%d",&n);
    for(reg int i=0;i<n;++i)
        a[i].Read();
    return;
}

inline Node GetMid(Node a,Node b){
    return Node((a.x+b.x)/2.0,(a.y+b.y)/2.0);
}

inline Node GetOp(reg int i){
    if(n&1)
        return GetMid(a[(i+n/2)%n],a[(i+n/2+1)%n]);
    else
        return a[(i+n/2)%n];
}

#define eps 1e-6

inline bool cmpT(Node c1,Node c2,Node a,Node b){
    return fabs((c1.y-c2.y)*(a.y-b.y)+(a.x-b.x)*(c1.x-c2.x))<eps;
}

inline bool cmpE(Node c1,Node c2,Node a,Node b){
    return fabs((c1.y-c2.y)*(a.x-b.x)-(a.y-b.y)*(c1.x-c2.x))<eps;
}

inline void Work(void){
    reg bool flag;
    reg int ans=0;
    if(n&1){
        for(reg int i=0;i<n;++i){
            flag=true;
            for(reg int j=1;j<=(n-1)/2;++j)
                if(!cmpT(a[i],GetOp(i),a[(i+j)%n],a[(i-j+n)%n])){
                    flag=false;
                    break;
                }
            if(flag)
                ++ans;
        }
    }
    else{
        for(reg int i=0;i<n/2;++i){
            flag=true;
            for(reg int j=1;j<=(n-1)/2;++j)
                if(!cmpT(a[i],GetOp(i),a[(i+j)%n],a[(i-j+n)%n])){
                    flag=false;
                    break;
                }
            if(flag)
                ++ans;
        }
        for(reg int i=0;i<n/2;++i){
            flag=true;
            for(reg int j=1;j<=(n-1)/2;++j)
                if(!cmpE(a[i],a[(i+1)%n],a[(i+j+1)%n],a[(i-j+n)%n])||!cmpT(a[i],a[(i+1)%n],GetMid(a[i],a[(i+1)%n]),GetMid(a[(i+j+1)%n],a[(i-j+n)%n]))){
                    flag=false;
                    break;
                }
            if(flag)
                ++ans;
        }
    }
    printf("%d\n",ans);
    return;
}

解法 B(正解)

思路

首先,对称轴分开的左右两边的图形全等,对应边相等,对应角也相等。

那么把多边形看作字符串,则可知此时构成了一个回文串。

也就是说我们可以使用 $\texttt{Manacher}$ 来解决这道题,算法的渐近时间复杂度为 $\Theta(n)$ 。

实现细节:

  1. 边长本质上与边长的平方没有区别,计算边长时无需开方。
  2. 角度无需计算出来,因为 $\theta\in[0,\pi]$ 时,$\theta$ 的余弦值与 $\theta$ 一一对应,所与可以用 $ \cos \theta $ 来代替,又因为我们先考虑长度,再考虑角度,所以 $\cos\theta$ 又可以用向量点乘的坐标表示来代替。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    int T=read();
    while(T--){
        Read();
        Work();
    }
    return 0;
}

struct Node{
    ll x,y;
    inline void Read(void){
        x=read(),y=read();
        return;
    }
};

int n;
Node a[MAXN];

inline void Read(void){
    n=read();
    for(reg int i=0;i<n;++i)
        a[i].Read();
    return;
}

inline ll GetLen(const Node& a,const Node& b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

inline ll GetAng(const Node& a,const Node& b,const Node& c){
    return (a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y);
}

ll s[MAXN<<2];
int len[MAXN<<2];

inline void Work(void){
    for(reg int i=0;i<n;++i){
        s[i<<1]=GetAng(a[(i-1+n)%n],a[i],a[(i+1)%n]);
        s[i<<1|1]=GetLen(a[i],a[(i+1)%n]);
    }
    for(reg int i=0;i<n;++i)
        s[i+(n<<1)]=s[i];
    reg int r=0,mid=0;
    for(reg int i=0;i<(n<<2);++i){
        if(i<r)
            len[i]=min(r-i,len[(mid<<1)-i]);
        else
            len[i]=1;
        while(i-len[i]>=0&&i+len[i]<(n<<2)&&s[i+len[i]]==s[i-len[i]])
            ++len[i];
        if(i+len[i]>r){
            r=i+len[i];
            mid=i;
        }
    }
    reg int ans=0;
    for(reg int i=0;i<(n<<2);++i)
        if(len[i]>=n+1)
            ++ans;
    printf("%d\n",ans);
    return;
}