#include using namespace std; namespace { #define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i) #define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i) #define VERA(x, seq) for (auto &x : seq) #define SIZE(x) ((ll)(x.size())) #define ALL(x) x.begin(), x.end() //types and constants typedef double T; //scalar type, change to long long or __int128 if needed typedef complex Pt; // can be point (x, y) or vector from (0,0) to (x,y) typedef pair Line; // can be line or line segment typedef vector Poly; //points should be in CW or CCW order and unique const T EPS = (T) (1e-10); //will be zero for integral T, change as needed /** * only need this if T is __int128 */ /*T Dist(T x) { return x < 0 ? -x : x; }*/ /** * Determines whether a is equal b, works for floating point and integral types */ bool eq(const T& a, const T& b) { return abs(a - b) <= EPS; } T cross(const Pt& a, const Pt& b) { return imag(conj(a) * b); } bool collinear(const Pt& a, const Pt& b) { return eq(cross(a, b), 0); } /** * finds intersecion of 2 lines * returns false on failure if lines are parallel and not equal * tested on https://open.kattis.com/problems/segmentintersection */ bool line_line(const Pt& a1, const Pt& a2, const Pt& b1, const Pt& b2, Pt& res) { const T det = cross(b2 - b1, a1 - a2); if (eq(det, 0)) { // parallel lines if (collinear(a1 - b1, a1 - b2)) { assert("Should be no 3 collinear points" && false); } return false; } const T t = cross(b2 - b1, a1 - b1) / det; res = a1 + (a2 - a1) * t; return true; } T Dist(const Pt& p) { return abs(p); // return sqrt(p.real() * p.real() + p.imag() * p.imag()); } typedef int ll; typedef double dd; const ll MAX = 202; const T INF = 1e20; T dp[MAX][MAX]; // distance to outer polygon point at edge (i, (i+1) % SIZE(inner)) T lef_dist[MAX], rig_dist[MAX]; T len[MAX]; Poly outer, inner; ll o_sz, i_sz; ll Succ(ll i) { return (i + 1) % i_sz; } ll Pred(ll i) { return (i - 1 + i_sz) % i_sz; } /** * @param lef * @param rig * @return min cost to cut if inner edge (lef-1) and edge (rig) are already cut */ T Rec(ll lef, ll rig) { T& res = dp[lef][rig]; if (res > 0) return res; if (lef == rig) return 0; res = INF; for (ll nx = lef; nx != rig; nx = Succ(nx)) { const Pt& a = inner[nx], b = inner[Succ(nx)]; T l_dist = lef_dist[nx], r_dist = rig_dist[nx]; Pt isec; // narrow cut if (line_line(a, b, inner[Pred(lef)], inner[lef], isec)) { const T da = Dist(isec - a), db = Dist(isec - b); assert(!eq(da, db)); if (da < db) l_dist = min(l_dist, da); else if (db < da) r_dist = min(r_dist, db); } if (line_line(a, b, inner[rig], inner[Succ(rig)], isec)) { const T da = Dist(isec - a), db = Dist(isec - b); assert(!eq(da, db)); if (da < db) l_dist = min(l_dist, da); else if (db < da) r_dist = min(r_dist, db); } const auto cut = l_dist + r_dist + len[nx]; res = min(res, cut + Rec(lef, nx) + Rec(Succ(nx), rig)); } return res; } Poly ReadPoly() { ll cnt; cin >> cnt; Poly poly(cnt); VERA(p, poly) { ll x, y; cin >> x >> y; p = Pt(x, y); } return poly; } void Solve(ll) { outer = ReadPoly(); inner = ReadPoly(); o_sz = SIZE(outer); i_sz = SIZE(inner); // for each inner edge, compute left and right intersection with outer polygon // should always exist, it is the intersection with an outer edge that is closest to the points // of the edge VEVE(i, 0, i_sz) { const Pt a = inner[i], b = inner[Succ(i)]; lef_dist[i] = rig_dist[i] = INF; len[i] = Dist(a - b); VEVE(j, 0, o_sz) { Pt isec; if (line_line(a, b, outer[j], outer[(j + 1) % o_sz], isec)) { const T da = Dist(isec - a), db = Dist(isec - b); assert(!eq(da, db)); if (da < db) { lef_dist[i] = min(lef_dist[i], da); } else if (db < da) { rig_dist[i] = min(rig_dist[i], db); } } } } memset(dp, 0, sizeof(dp)); T res = INF; VEVE(i, 0, i_sz) { const auto cut = lef_dist[i] + rig_dist[i] + len[i]; res = min(res, cut + Rec(Succ(i), i)); } cout << fixed << setprecision(7) << res << endl; } void Init() { ios::sync_with_stdio(false); cin.tie(nullptr); } } int main() { #ifdef AZN freopen("input.txt", "r", stdin); #endif Init(); ll tests = 1; VEVE(test, 1, tests + 1) Solve(test); return 0; }