首页 > 代码库 > BZOJ1100 对称轴osi （回文串）
BZOJ1100 对称轴osi （回文串）
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1100
分析：将多边形转化为如下的环：
角度0->0到1的边长->角度1->1到2的边长->...->角度n-1->n-1到0的边长。将其存到s中，再将s复制一遍存到后面。
然后枚举对称轴i，无非在边或顶点上，如果i为对称轴，那么[i-n,i+n]是一个回文串。
用Manacher算法算出以i为对称轴的最长回文串向左或右延伸的最大长度（包括i），当大于n时，说明以i为轴，两侧对应的边长和角度都相等，对称轴计数+1（ps：联想下铁拉门）。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100000 + 5; 7 8 int x[maxn], y[maxn], s[maxn << 2], p[maxn << 2]; 9 10 inline int dis(const int& a, const int& b) {11 return (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);12 }13 14 inline int cross(const int& a, const int& b, const int& c) {15 return (x[b] - x[a]) * (y[c] - y[a]) - (x[c] - x[a]) * (y[b] - y[a]);16 }17 18 int main() {19 int t;20 scanf("%d", &t);21 while (t--) {22 int n;23 scanf("%d", &n);24 for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);25 for (int i = 0; i < n; i++) s[i << 1 | 1] = dis(i, (i + 1) % n);26 for (int i = 0; i < n; i++) s[i << 1] = cross(i, (i - 1 + n) % n, (i + 1) % n);27 int all = n << 1; for (int i = 0; i < n; i++) s[all + i] = s[i]; all <<= 1;28 int ans = 0, mx = 0, id = 0; memset(p, 0, sizeof(p));29 for (int i = 0; i < all; i++) {30 p[i] = mx > i ? min(p[id * 2 - i], mx - i) : 1;31 while (i - p[i] >= 0 && i + p[i] < all && s[i - p[i]] == s[i + p[i]]) p[i]++;32 if (i + p[i] > mx) { mx = i + p[i]; id = i; }33 if (p[i] > n) ans++;34 }35 printf("%d\n", ans);36 }37 return 0;38 }
BZOJ1100 对称轴osi （回文串）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。