解题思路

问题分析 判断两个多边形是否相似，等价于判断它们的顶点序列是否满足相似变换（平移、旋转、缩放）的条件。相似变换可以分解为以下步骤：

平移：将多边形的顶点平移，使第一个顶点与原点重合。 缩放与旋转：通过计算向量的比例和角度，判断剩余顶点是否满足相同的缩放因子和旋转角度。 关键步骤 平移归一化：将两个多边形的顶点平移，使第一个顶点为原点。例如，对于多边形A的顶点$(x_i, y_i)$，平移后为$(x_i - x_0, y_i - y_0)，其中(x_0, y_0)$是第一个顶点。 向量表示：将平移后的顶点视为从原点出发的向量，计算相邻向量的比例和夹角。 相似性判断： 计算第一个多边形的基准向量（如前两个顶点的向量）。 对第二个多边形的向量，计算其与基准向量的缩放因子和旋转角度，并验证后续向量是否满足相同的变换。

cpp

#include <math.h> #include <stdio.h> #define eps 1e-6 #define sqr(x) ((x) * (x)) #define same(a, b) (fabs((a) - (b)) < eps) #define dis2(a, b) (sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)))

struct point { double x, y; point operator-(point &b) { point c; c.x = x - b.x; c.y = y - b.y; return c; } }; double dot(point a, point b) { return a.x * b.x + a.y * b.y; } double cross(point a, point b) { return a.x * b.y - a.y * b.x; } double get_anlge(point p1, point p2, point p3) { //不需要求反余弦,点击相当，反余弦相等,避免使用反三角函数 return dot(p1 - p2, p3 - p2) / dis2(p1, p2) / dis2(p2, p3); } int get_dir(point p1, point p2, point p3) { //根据三点得到转向 double t1 = cross(p2 - p1, p3 - p2); if(fabs(t1) < eps) return 1; if(t1 < 0) return 2; else return 3; } int slove(double ang1[], double ang2[], double len1[], double len2[], int dir1[], int dir2[], int n) { /由于题目已经告诉了对应点的匹配顺序，所以只需要从 0，开始匹配，如果没有告诉对应的匹配顺序，就还有枚举 匹配对应边/ int s, t, k; s = 0; t = 0; for(k = 0; k < n; k++) { if(!same(ang1[s], ang2[t]) || !same(len1[s], len2[t]) || dir1[s] != dir2[t]) break; s++; t++; s %= n; t %= n; } if(k == n) return 1; return 0; }

double polygonArea(point p[], int n) { //已知多边形各顶点的坐标，求其面积 double area = 0.0; for(int i = 1; i <= n; i++) area += (p[i - 1].x * p[i % n].y - p[i % n].x * p[i - 1].y); return area; }

int main() { int n, similar; point p1[20], p2[20]; double max1, max2; double ang1[20], ang2[20], len1[20], len2[20]; int dir1[20], dir2[20]; while(scanf("%d", &n) && n) { for(int i = 0; i < n; i++) { scanf("%lf%lf", &p1[i].x, &p1[i].y); } for(int i = 0; i < n; i++) { scanf("%lf%lf", &p2[i].x, &p2[i].y); } ang1[0] = get_anlge(p1[n - 1], p1[0], p1[1]); ang2[0] = get_anlge(p2[n - 1], p2[0], p2[1]); dir1[0] = get_dir(p1[n - 1], p1[0], p1[1]); dir2[0] = get_dir(p2[n - 1], p2[0], p2[1]); for(int i = 1; i < n; i++) { ang1[i] = get_anlge(p1[i - 1], p1[i], p1[(i + 1) % n]); ang2[i] = get_anlge(p2[i - 1], p2[i], p2[(i + 1) % n]); dir1[i] = get_dir(p1[i - 1], p1[i], p1[(i + 1) % n]); dir2[i] = get_dir(p2[i - 1], p2[i], p2[(i + 1) % n]); } max1 = -1, max2 = -1; for(int i = 0; i < n; i++) { len1[i] = dis2(p1[i], p1[(i + 1) % n]); if(len1[i] > max1) max1 = len1[i]; len2[i] = dis2(p2[i], p2[(i + 1) % n]); if(len2[i] > max2) max2 = len2[i]; } for(int i = 0; i < n; i++) { len1[i] /= max1; len2[i] /= max2; } if(slove(ang1, ang2, len1, len2, dir1, dir2, n)) printf("similar\n"); else printf("dissimilar\n"); } return 0; }