网站开发总体功能设计,医疗网站不备案,恩施网站制作公司,东营市东营网站设计题意#xff1a;给一个 nnn 个点的多边形#xff0c;求对称轴个数。 n≤105n\leq 10^5n≤105
显然对称轴一定在顶点或边的中点上。
但你 n2n^2n2 枚举完全没有一点能过的样子。
冷静分析#xff0c;发现有 “中点”#xff0c;“对称轴”#xff0c;很自然个鬼地想到了…题意给一个 nnn 个点的多边形求对称轴个数。
n≤105n\leq 10^5n≤105
显然对称轴一定在顶点或边的中点上。
但你 n2n^2n2 枚举完全没有一点能过的样子。
冷静分析发现有 “中点”“对称轴”很自然个鬼地想到了manacher。
在边的中点插入一个点然后复制一遍断环成链。 然后跑马拉车扩展的时候判断是否轴对称。
设点 iii 可以扩展到 [i−pi,ipi][i-p_i,ip_i][i−pi,ipi]如果扩展到整个多边形就是合法的对称轴即 2pi1≥2n2p_i1\geq 2n2pi1≥2npi≥np_i\geq npi≥n并且只有第一圈的点会有贡献。一个对称轴会算两次除以 222 就是答案。
方便实现的小trick
边界的地方随机一个点就不用特判。判轴对称可以算出中点用叉积判在不在已知的对称轴上。如果对称轴未确定就设成 000 向量。但要注意本来就确定的时候要特判一下不要把它改回零向量。读入的坐标都乘上 444就可以不用 double。
复杂度 O(n)O(n)O(n)
#include iostream
#include cstdio
#include cstring
#include cctype
#include cstdlib
#define MAXN 400005
using namespace std;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) (c-)(f-1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
typedef long long ll;
int x[MAXN],y[MAXN];
int p[MAXN],maxr,mid,cnt;
int lasx,lasy;
inline bool check(int l,int i,int r)
{if ((ll)(x[l]-x[i])*(x[l]-x[i])(ll)(y[l]-y[i])*(y[l]-y[i])!(ll)(x[r]-x[i])*(x[r]-x[i])(ll)(y[r]-y[i])*(y[r]-y[i]))return false;int tx(x[l]x[r])/2-x[i],ty(y[l]y[r])/2-y[i];if ((ll)tx*lasy!(ll)ty*lasx) return false;if ((ll)tx*tx(ll)ty*ty) lasxtx,lasyty;return true;
}
int main()
{for (int Tread();T;T--){int nread();for (int i1;i2*n;i2) x[i]read()*4,y[i]read()*4;for (int i2*n1;i4*n;i2) x[i]x[i-2*n],y[i]y[i-2*n];x[4*n1]x[1],y[4*n1]y[1];for (int i2;i4*n;i2) x[i](x[i-1]x[i1])/2,y[i](y[i-1]y[i1])/2;x[0]rand(),y[0]rand(),x[4*n1]rand(),y[4*n1]rand();maxrmidcnt0;for (int i1;i4*n;i){if (imaxr) p[i]min(p[2*mid-i],maxr-i);else p[i]0;lasxlasy0;while (check(i-p[i]-1,i,ip[i]1)) p[i];if (ip[i]maxr) maxrip[i],midi;cnt(p[i]n);}printf(%d\n,cnt/2);}return 0;
}
