AOJ1164.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long double ld;
typedef complex<ld> P;
const ld INF = 1e9, eps = 1e-9, pi = acos(-1.0);

template<typename T> T chmin(T &a, T b) { return a = min(a, b); }

namespace std {
  bool operator<(const P &l, const P &r) { return l.real() < r.real(); }
}

const P rnd = P(cos(1), sin(1));

P input() {
  ld x, y; cin >> x >> y;
  return P(x, y) * rnd;
}

ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }

struct L{ P a, b; };

P is_ll(L s, L t){
  P sv = s.b - s.a, tv = t.b - t.a;
  return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

bool isis_sp(L s, P p) {
  return abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps;
}

bool isis_ss(L s, L t) {
  if (abs(cross(s.b - s.a, t.b - t.a)) < eps) return false;
  P p = is_ll(s, t);
  return isis_sp(s, p) && isis_sp(t, p);
}

pair<ld,vector<int>> upd[128][128];

vector<int> conv(vector<int> v) {
  vector<int> res;
  for (int i: v) {
    if (!res.empty() && res.back() == i) res.pop_back();
    else res.push_back(i);
  }
  return res;
}

int main() {
  int M, N;
  while (cin >> M >> N, M) {
    vector<P> seg(M), pile(N);
    REP(i,M) seg[i] = input();
    REP(i,N) pile[i] = input();
    sort(ALL(pile));
    vector<int> visit;
    REP(i,M-1) {
      vector<int> v;
      L s = (L){seg[i], seg[i+1]};
      REP(j,N) {
        if (isis_ss((L){pile[j], pile[j] + P(0, 1e5)}, s)) v.push_back(j*2);
        if (isis_ss((L){pile[j] + P(0, -1e5), pile[j]}, s)) v.push_back(j*2+1);
      }
      if (seg[i+1] < seg[i]) reverse(ALL(v));
      visit.insert(end(visit), ALL(v));
    }
    visit.push_back(2 * N + 2);
    visit = conv(visit);
    REP(i,128) REP(j,128) upd[i][j].second.clear();
    pile.push_back(seg.front());
    pile.push_back(seg.back());
    REP(i,N+2) REP(j,N+2) {
      if (i == j) continue;
      L s = (L){pile[i], pile[j]};
      vector<int> v;
      REP(k,N) {
        if (i == k || j == k) continue;
        if (isis_ss((L){pile[k], pile[k] + P(0, 1e5)}, s)) v.push_back(k*2);
        if (isis_ss((L){pile[k] + P(0, -1e5), pile[k]}, s)) v.push_back(k*2+1);
      }
      if (pile[j] < pile[i]) reverse(ALL(v));
      upd[i][j] = make_pair(abs(pile[i] - pile[j]), v);
    }
    vector<vector<ld>> dp(visit.size() + 1, vector<ld>(N+2, INF)); dp[0][N] = 0;
    REP(p,visit.size()) REP(i,N+2) REP(j,N+2) {
      if (dp[p][i] == INF) continue;
      bool flag = true;
      for (int k = 0, q = p;
           k < (int)upd[i][j].second.size() && q < (int)visit.size() && flag;
           ++k, ++q) {
        if (upd[i][j].second[k] != visit[q]) flag = false;
      }
      if (flag && ((j > N && p + upd[i][j].second.size() == visit.size()) ||
                   (p + upd[i][j].second.size() < visit.size() &&
                    visit[p + upd[i][j].second.size()] / 2 == j)))
        chmin(dp[p + upd[i][j].second.size() + 1][j], dp[p][i] + upd[i][j].first);
    }
    ld res = INF;
    REP(i,N+2) res = min(res, dp.back()[i]);
    cout << setprecision(12) << fixed << res << endl;
  }
  return 0;
}