#ifndef LOCAL //~ #pragma GCC optimize("O3") #endif #include using namespace std; #define sim template muu & operator<<( #define ris return *this #define R22(r) sim> typename enable_if<1 r sizeof(dud(0)),muu&>::type operator<<(c g) { sim> struct rge {c b, e;}; sim> rge range(c i, c j) {return rge{i, j};} sim> auto dud(c*r)->decltype(cerr << *r); sim> char dud(...); struct muu { #ifdef LOCAL stringstream a; ~muu() {cerr << a.str() << endl;} R22(<) a << boolalpha << g; ris;} R22(==) ris << range(begin(g), end(g));} sim mor rge u) { a << "["; for (c i = u.b; i != u.e; ++i) *this << ", " + 2 * (i == u.b) << *i; ris << "]"; } sim, class b mor pair r){ris << "(" << r.first << ", " << r.second << ")";} #else sim mor const c&){ris;} #endif }; #define debug muu() << __FUNCTION__ << "#" << __LINE__ << ": " #define imie(r...) "[" #r ": " << (r) << "] " #define range(a, b) "[[" #a ", " #b "): " << range(a, b) << "] " #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] " using ll = long long; using ld = long double; using pii = pair ; const int nax = 410; int n; #define x first #define y second pii p[nax]; struct L { ld a, b, c; }; muu & operator<<(muu &d, L x) {return d << "[" << x.a << ", " << x.b << ", " << x.c << "]";} ld vec(pii a, pii b) { return a.first * (ld) b.second - a.second * (ld) b.first; } L make_line(pii a, pii b) { return L{a.y - b.y, b.x - a.x, vec(b, a)}; } const ld eps = 1e-9; using P = pair ; vector

inter(L k, L l) { #define Q(i, j) ((ld)k.i * l.j - (ld)k.j * l.i) ld det = Q(a, b); if (abs(det) < 1e-10) return {}; vector

ans = {{Q(c, b) / det, Q(a, c) / det}}; debug << imie(k) imie(l) imie(ans); return ans; } bool in(P o) { int above = 0; for (int i = 0; i < n; ++i) { int i1 = (i + 1) % n; if (p[i].x == p[i1].x && p[i].x > o.x + eps) { //~ debug << arr(p, i) arr(p, i1); if (p[i].y > o.y) { //~ debug << arr(p, i) "above++"; above++; } if (p[i1].y > o.y) { above--; //~ debug << arr(p, i1) "above--"; } } } //~ debug << imie(o) imie(above); //~ assert(above == 0 || above == -1); return above != 0; } bool in(ld x1, ld x2, ld y1, ld y2) { for (int i = 0; i < n; ++i) { if (p[i].x >= x1 - eps && p[i].x - eps <= x2 && p[i].y >= y1 - eps && p[i].y - eps <= y2) { return false; } int i1 = (i + 1) % n; if (p[i].x >= x1 - eps && p[i].x - eps <= x2 && p[i1].x - eps <= x2 && p[i1].x >= x1 - eps) { if (p[i].y < y2 && p[i1].y > y1) return false; if (p[i1].y < y2 && p[i].y > y1) return false; } if (p[i].y - eps <= y2 && p[i].y >= y1 - eps && p[i1].y - eps <= y2 && p[i1].y >= y1 - eps) { if (p[i].x - eps < x2 && p[i1].x > x1 - eps) return false; if (p[i1].x - eps < x2 && p[i].x > x1 - eps) return false; } } return true; } ld distm(P a, P b) { return max(abs(a.x - b.x), abs(a.y - b.y)); } pii make_r(int a, int b) { return {min(a, b), max(a, b)}; } bool in(ld x, pii r) { return x >= r.first - eps && x <= r.second + eps; } ld alt(P x) { if (!in(x)) return 0; ld ans = 1e9; for (int i = 0 ; i < n; ++i) { int i2 = (i + 1) % n; ans = min(ans, distm(x, p[i])); pii xr = make_r(p[i].x, p[i2].x); pii yr = make_r(p[i].y, p[i2].y); if (in(x.x, xr)) ans = min(ans, abs(x.y - p[i].y)); if (in(x.y, yr)) ans = min(ans, abs(x.x - p[i].x)); } #ifdef LOCAL ld low = 0, high = 1e5; for (int i = 0; i < 40; ++i) { ld med = (low + high) / 2; if (in(x.first - med, x.first + med, x.second - med, x.second + med)) low = med; else high = med; } debug << imie(x) imie(low) imie(ans); assert(abs(low - ans) < 1e-5); #endif return ans; } ld dist(P a, P b) { ld v = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); ld h = alt(a) - alt(b); ld r = sqrt(v + h * h); debug << imie(a) imie(b) imie(h) imie(r); return r; } pii operator+(pii a, pii b) { return {a.first + b.first, a.second + b.second}; } ld val(pii me, pii they, P wh) { int ax = (me.x - they.x); int ay = (me.y - they.y); return wh.first * (ax + 1) + wh.second * ay; } P mid(P a, P b) { return {(a.first + b.first) / 2, (a.second + b.second) / 2}; } int main() { scanf("%d", &n); pii me, they; scanf("%d%d%d%d", &me.first, &me.second, &they.first, &they.second); for (int i = 0; i < n; ++i) scanf("%d%d", &p[i].first, &p[i].second); L path = make_line(me, they); vector > special; for (int i = 0; i < n; ++i) { vector dx = {{0, 1}, {1, 1}, {1, 0}, {1, -1}}; for (pii d : dx) { pii pp = p[i]; pii p2 = pp + d; L sp = make_line(pp, p2); auto r = inter(sp, path); for (auto rr : r) special.emplace_back(rr, false); } } set xes, yes; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { xes.insert(p[i].x + p[j].x); yes.insert(p[i].y + p[j].y); } } for (int x : xes) { L li{1, 0, x * (ld) 0.5}; vector

is = inter(li, path); for (P p : is) special.emplace_back(p, false); } for (int y : yes) { L li{0, 1, y * (ld) 0.5}; vector

is = inter(li, path); for (P p : is) special.emplace_back(p, false); } special.emplace_back(P(me.x, me.y), true); special.emplace_back(P(they.x, they.y), true); using T = pair ; sort(special.begin(), special.end(), [me, they](T a, T b){return val(me, they, a.first) < val(me, they, b.first);}); debug << imie(special); int seen = 0; int len = special.size(); for (int i = 0; i < len - 1; ++i) { P f = mid(special[i].first, special[i + 1].first); special.emplace_back(f, false); } sort(special.begin(), special.end(), [me, they](T a, T b){return val(me, they, a.first) < val(me, they, b.first);}); len = special.size(); ld ans = 0; for (int i = 0; i < len - 1; ++i) { seen += special[i].second ? 1 : 0; if (seen == 1) { ans += dist(special[i].first, special[i + 1].first); } } printf("%.10Lf\n", ans); debug << imie(in(P(1, 1))); }