计算一下，对于主人经过一段路线，宠物来得及跑到哪些景点再跑回来。然后对于主人的一段路程看作一个点，与来得及的景点连边。跑一下匈牙利算法就可以了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 bool flg[110]; 6 int a[110][2],b[110][2]; 7 int mth[110],res[110],head[110],to[11000],nxt[11000]; 8 int cnt,n,m,ans; 9 bool find(int x)  10 {  11     for (int i = head[x];i;i = nxt[i])  12     {  13         if (flg[to[i]] == false)  14         {  15             flg[to[i]] = true;  16             if (find(mth[to[i]]) || mth[to[i]] == 0)  17             {  18                 mth[to[i]] = x;19                 res[x] = to[i];  20                 return true;  21             }  22         }  23     }  24     return false;  25 }  26 void match()27 {28     for (int i = 1;i <= n - 1;i++)29     {30         memset(flg,0,sizeof(flg));31         if (find(i))32              ans++;33     }34 }35 void add(int x,int y)36 {37     nxt[++cnt] = head[x];38     to[cnt] = y;39     head[x] = cnt;40 }41 int sqr(int x)42 {43     return x * x;44 }45 double dis(int x1,int y1,int x2,int y2)46 {47     return sqrt(sqr(x2 - x1) + sqr(y2 - y1));48 }49 int main()50 {51     scanf("%d%d",&n,&m);52     ans = n;53     for (int i = 1;i <= n;i++)54         scanf("%d%d",&a[i][0],&a[i][1]);55     for (int i = 1;i <= m;i++)56         scanf("%d%d",&b[i][0],&b[i][1]);57     for (int i = 1;i <= n - 1;i++)58         for (int j = 1;j <= m;j++)59             if (2 * dis(a[i][0],a[i][1],a[i + 1][0],a[i + 1][1]) >= dis(a[i][0],a[i][1],b[j][0],b[j][1]) + dis(a[i + 1][0],a[i + 1][1],b[j][0],b[j][1]))60                 add(i,j);61     match();62     printf("%d\n",ans);63     for (int i = 1;i <= n;i++)64     {65         printf("%d %d ",a[i][0],a[i][1]);66         if (res[i] != 0)67             printf("%d %d ",b[res[i]][0],b[res[i]][1]); 68     }69     return 0;70 }