题目分析与解题思路

问题描述

给定一个模板折线和多个目标折线，要求找出所有与模板折线具有相同形状的目标折线。相同形状定义为：通过平移、旋转（任意角度）后，折线能完全重叠。折线由一系列顶点定义，相邻线段始终垂直（90度转弯），且不重复经过同一点。顶点顺序可正序或逆序（即起点到终点或终点到起点）。

输入格式

• 多组数据，以 0 结束。
• 每组数据：
  • n：目标折线数量（1 ≤ n ≤ 50）。
  • 模板折线：第一行为顶点数 m，随后 m 行每行是坐标 (x, y)。
  • n 个目标折线：格式同模板。

输出格式

• 对每组数据，输出匹配模板的目标折线编号（升序），每行一个编号，最后输出 +++++。

关键算法思路

1. 形状相同的判定条件

• 平移不变性：通过将折线平移到原点（所有点减去起点坐标）消除平移影响。
• 旋转不变性：旋转角度为 90° 的整数倍（0°、90°、180°、270°）。旋转后，线段长度不变，但方向变化（水平变垂直等）。
• 方向反转兼容性：顶点顺序可逆序（从终点到起点），此时线段方向反转，转弯方向取反。

2. 核心比较方法：向量叉积与长度匹配

• 步骤一：预处理折线

  • 计算相邻顶点的线段向量（如模板顶点 A→B 的向量为 (B.x - A.x, B.y - A.y)）。
  • 存储各线段长度平方（避免浮点误差）和转弯方向（用叉积符号表示）。

• 步骤二：比较目标与模板

  • 长度匹配：检查目标折线各线段长度是否与模板一致。
  • 转弯方向匹配：
    • 转弯方向由相邻线段的叉积符号表示（>0 表示左转，<0 表示右转）。
    • 叉积符号的旋转不变性：旋转后叉积绝对值不变，符号可能反转（需兼容）。
    • 逆序处理：目标折线顶点逆序时，线段向量取反，叉积符号反转。

3. 算法流程

1. 读取数据：解析模板和所有目标折线的顶点坐标。
2. 顶点数过滤：若目标折线顶点数与模板不同，直接跳过。
3. 向量与叉积计算：
   • 对模板和目标折线：
     • 计算平移后的线段向量。
     • 计算线段长度平方序列。
     • 计算相邻向量的叉积序列（表示转弯方向）。
4. 双向匹配：
   • 正序匹配：比较目标与模板的长度序列和叉积序列。
   • 逆序匹配：目标折线顶点逆序，并取反向量后，比较长度序列和叉积序列。
5. 输出结果：匹配成功则输出目标编号，每组数据结束输出 +++++。

代码示例

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<string>
 #include<algorithm>
 #include<vector>
 #include<queue>
 #include<stack>
 using namespace std;
 #define LL __int64
 #define pii pair<int,int>
 #define Max(a,b) ((a)>(b)?(a):(b))
 #define Min(a,b) ((a)<(b)?(a):(b))
 #define mem(a,b) memset(a,b,sizeof(a))
 #define lson l,mid,rt<<1
 #define rson mid+1,r,rt<<1|1
 const int N=55,INF=0x3f3f3f3f,MOD=100000000;
 const double DNF=100000000000;
 
 struct Node{
     double x,y;
 }nod[N][12];
 
 int n,cou[N];
 
 double dist(Node &a)
 {
     return a.x*a.x+a.y*a.y;
 }
 
 void getr(Node& r,Node& a,Node& b)
 {
     r.x=a.x-b.x;
     r.y=a.y-b.y;
 }
 
 double cha(Node& r1,Node& r2)
 {
     return r1.x*r2.y-r2.x*r1.y;
 }
 
 int judge(int k,int sta,int dir)
 {
     int i,j;
     Node r0,rj,r01,rj1;
     for(i=1,j=sta+dir;i<cou[0];i++,j+=dir){
         getr(r0,nod[0][i],nod[0][i-1]);
         getr(rj,nod[k][j],nod[k][j-dir]);
         if(dist(r0)!=dist(rj))return 0;
         if(i<cou[0]-1){
             getr(r01,nod[0][i+1],nod[0][i]);
             getr(rj1,nod[k][j+dir],nod[k][j]);
             if(cha(r01,r0)!=cha(rj1,rj))return 0;
         }
     }
     return 1;
 }
 
 int main()
 {
  //   freopen("in.txt","r",stdin);
     int i,j;
     while(~scanf("%d",&n) && n)
     {
         for(i=0;i<=n;i++){
             scanf("%d",&cou[i]);
             for(j=0;j<cou[i];j++)
                 scanf("%lf%lf",&nod[i][j].x,&nod[i][j].y);
         }
 
         for(i=1;i<=n;i++){
             if(cou[i]!=cou[0])continue;
             if(judge(i,0,1) || judge(i,cou[i]-1,-1))
                 printf("%d\n",i);
         }
         printf("+++++\n");
     }
     return 0;
 }

代码实现要点

1. 数据结构：

   • 存储折线顶点坐标。
   • 向量序列：vector<pair<double, double>>。
   • 长度序列与叉积序列：vector<double>。

2. 关键函数：

   • getVector()：计算两点间向量。
   • crossProduct()：计算叉积。
   • isMatch()：比较长度序列和叉积序列（支持正序/逆序）。

3. 浮点精度处理：

   • 坐标整数特性，长度平方和叉积用整数运算避免误差。
   • 叉积比较时使用 fabs(a - b) < 1e-7 容差。

4. 复杂度：

   • 时间：每组数据 O(n × m)（n 目标数，m 顶点数）。
   • 空间：O(n × m) 存储折线数据。