Submission #1212606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212606		og_matveychick1	Fences (JOI18_fences)	C++20	18 / 100	79 ms	3396 KiB

fences

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

// /*
//                                                //////////**DEFINES - START**//////////

#define ret return
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define be(x) x.begin()
#define en(x) x.end()
#define sz(x) ll(x.size())
#define for0(i, n) for (ll   i = 0; i < (n); ++i)
#define for1(i, n) for (ll   i = 1; i < (n); ++i)
#define rfor0(i, n) for (ll   i = (n) - 1; i >= 0; --i)
#define rfor1(i, n) for (ll   i = (n) - 1; i >= 1; --i)
#define rep(i, a, n) for (ll   i = a; i < ll(n); ++i)
#define rrep(i, a, n) for (ll   i = a - 1; i >= ll(n); --i)
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define fastIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define con continue
#define pb push_back
#define pob pop_back
#define deb(x) cout << (#x) << " is " << (x) << endl
#define ins insert
#define len(s) (s).length()
#define gi greater<int>()
#define gll greater<ll  >()
#define gstr greater<string>()
#define gpll greater<pair<ll  , ll  >>()
#define rast(x1, y1, x2, y2) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
#define rev reverse
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define rs resize
#define last(a) a.back()
#define co count
#define ba(a) a.back()
#define um unordered_map
#define rsun(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define endl '\n'
#ifdef OG_Matveychick1
bool local = true;
#else
bool local = false;
#endif

//                                                \\\\\\\\\\**DEFINES - END**\\\\\\\\\\
        // */

// /*
//                                                //////////**TYPEDEFS - START**//////////

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ull> vull;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef pair<double, double> pdd;
typedef double ld;
typedef double D;
typedef vector<ld> vld;
typedef vector<pair<ld, ld>>
        vpld;
typedef string str;
typedef set<ll> sll;
typedef set<int> si;
typedef set<str> ss;
typedef set<pii> spii;
typedef multiset<int> msi;
typedef multiset<ll> msll;
typedef multiset<str> mss;
typedef multiset<pii> mspii;
typedef multiset<pll> mspll;
typedef map<str, str> mps;
typedef map<int, int> mpi;
typedef map<ll, ll> mpll;
typedef map<int, vi> mpvi;
typedef map<int, vll> mpvll;
typedef map<char, int> mpci;
typedef multimap<ll, ll> mmpll;
typedef multimap<str, str> mmps;
typedef multimap<int, int> mmpi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<long double>> vvld;
typedef vector<vvi> vvvi;
typedef vector<vector<char>> vvc;
typedef vector<vs> vvs;
typedef vector<D> vD;
typedef set<pair<ll, ll>>
        spll;
typedef pair<ull, ull> pull;
typedef vector<pull> vpull;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<char> sc;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<bool> qb;
typedef vector<sll> vsll;
typedef queue<pair<ll, ll>>
        qpll;
typedef vector<vector<pair<int, int>>>
        vvpii;
typedef vector<vector<pair<ll, ll>>>
        vvpll;
typedef vector<spll> vspll;
typedef multiset<char> msc;
typedef queue<str> qs;
typedef vector<set<int>> vsi;
typedef priority_queue<ll> pqll;
typedef vector<vsll> vvsll;
typedef pair<ld, ld> pld;
typedef vector<vvll> vvvll;
typedef set<ld> sld;
typedef vector<vpld> vvpld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_multiset;

//                                                \\\\\\\\\\**TYPEDEFS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**CONSTANTS - START**//////////

const ld pi = acosl(-1);
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll MAXLL = 9223372036854775807;
//const ll MAXINT = 2147483647;
const ld eps = 1e-6;

//                                                \\\\\\\\\\**CONSTANTS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**TEMPLATES - START**//////////


template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (T &i: a) in >> i;
    return in;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
    in >> a.fi >> a.se;
    return in;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
    out << a.fi << " " << a.se;
    return out;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> &i
            : a)
        in >> i.fi >> i.
                se;
    return
            in;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (auto i: a) {
        out << i << " ";
    }
    return out;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> i
            : a)
        out << i.fi << " " << i.se <<
            endl;
    return
            out;
}

template<typename T1>
ostream &operator<<(ostream &out, vector<vector<T1>> &a) {
    for (vector<T1> i: a) {
        for (T1 j: i) out << j << " ";
        out << endl;
    }
    return out;
}

template<typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? b : a;
}

template<typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? a : b;
}

template<typename T1, typename T2>
inline void amin(T1 &a, T2 b) {
    a = min(a, b);
}

template<typename T1, typename T2>
inline void amax(T1 &a, T2 b) {
    a = max(a, b);
}


//                                                \\\\\\\\\\**TEMPLATES - END**\\\\\\\\\\
        // */


// This bear is a good alternative to duck!!!
/*
    ????      ??????
  ???????????????????
 ????????????????  ???
???   ???????????  ???
???  ???????????? ??
 ??????????????????
   ??????????????? ?
   ?????????????????
   ???????   ???    ??
    ????  ??????????
     ????     ?? ???
   ???????????? ?????
  ????????????????????
 ????????   ??  ???????
 ???????         ?????
 */


ld getTime() {
    return (ld) clock() / (ld) CLOCKS_PER_SEC;
}


mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rn(4);

ll rnd(ll l, ll r) {
    ll a = rn() % (r - l + 1) + l;
    return a;
}

void solve();

ll T = 1;

signed main(int argc, char **argv) {
    //    setlocale(LC_ALL, "RUS");
    fastIO()
    cout.precision(12);
    cout << fixed;
    if (local && argc == 1) {
        freopen("input.txt", "r", stdin);
        //        freopen("output.txt", "w", stdout);
    }
//    cin >> T;
    while (T--) {
        solve();
    }
    if (local && argc == 1) {
        cout << endl << fixed << "time = " << getTime();
    }
    return 0;
}


/*
    ___        __              __   ______          __        _____ __             __          __  __
   /   | _____/ /___  ______ _/ /  / ____/___  ____/ /__     / ___// /_____ ______/ /______   / / / /__  ________
  / /| |/ ___/ __/ / / / __ `/ /  / /   / __ \/ __  / _ \    \__ \/ __/ __ `/ ___/ __/ ___/  / /_/ / _ \/ ___/ _ \
 / ___ / /__/ /_/ /_/ / /_/ / /  / /___/ /_/ / /_/ /  __/   ___/ / /_/ /_/ / /  / /_(__  )  / __  /  __/ /  /  __/
/_/  |_\___/\__/\__,_/\__,_/_/   \____/\____/\__,_/\___/   /____/\__/\__,_/_/   \__/____/  /_/ /_/\___/_/   \___/
*/



using num = ld;

struct vec {
    num x, y;

    vec(num x, num y) : x(x), y(y) {}

    vec() : x(0), y(0) {}

    bool operator==(vec a) {
        ret abs(a.x - x) < eps && abs(a.y - y) < eps;
    }

    void operator+=(vec a) {
        x += a.x;
        y += a.y;
    }

    vec operator+(vec a) {
        ret {x + a.x, y + a.y};
    }

    void operator-=(vec a) {
        x -= a.x;
        y -= a.y;
    }

    vec operator-(vec a) {
        ret {x - a.x, y - a.y};
    }

    void operator*=(vec a) {
        x *= a.x;
        y *= a.y;
    }

    vec operator*(num a) {
        ret {x * a, y * a};
    }

    num operator*(vec a) {
        ret x * a.x + y * a.y;
    }

    void operator*=(num a) {
        x *= a;
        y *= a;
    }

    void operator/=(num a) {
        x /= a;
        y /= a;
    }

    num operator%(vec a) {
        ret x * a.y - y * a.x;
    }

    num len2() {
        ret x * x + y * y;
    }

    friend istream &operator>>(istream &in, vec &a) {
        in >> a.x >> a.y;
        ret in;
    }

    friend ostream &operator<<(ostream &out, vec a) {
        out << a.x << " " << a.y << " ";
        ret out;
    }

    num napr(vec a) {
        if ((*this) % a > 0)ret 1;
        else if ((*this) % a < 0)ret -1;
        else
            ret 0;
    }

    ld angle(vec a) {
        ret atan2l(a % *this, a * *this);
    }

    ld polar_angle() {
        ret atan2l(y, x);
    }

    bool point_in_ray(vec a) //точка
    {
        ret (abs(*this % a - 0) < eps && *this * a >= -eps);
    }

    bool point_in_square_ray(vec a) //точка
    {
        ret (*this * a >= 0);
    }

    bool point_in_line(vec a) //точка
    {
        ret (*this % a == 0);
    }

    bool point_in_segment(vec a) //точка
    {
        ret (abs(*this % a - 0) < eps && *this * a >= -eps && vec(0 - x, 0 - y) * vec(a.x - x, a.y - y) >= -eps);
    }

    bool point_in_square_segment(vec a) //точка
    {
        ret (*this * a >= 0 && vec(0 - x, 0 - y) * vec(a.x - x, a.y - y) >= 0);
    }

    bool point_in_angle(vec a, vec b) //две крайние точки угла
    {
        ret (a.napr(b) * a.napr(*this) >= 0 && b.napr(a) * b.napr(*this) >= 0);
    }

    ld dist_from_point_to_line(vec a) //точка
    {
        ret *this % a / sqrt(len2());
    }

    ld dist_from_point_to_ray(vec a) //точка
    {
        ret (point_in_square_ray(a) ? *this % a / sqrtl(len2()) : min(sqrtl(vec(a).len2()),
                                                                      sqrtl(vec(a - *this).len2())));
    }

    ld dist_from_point_to_segment(vec a) //точка
    {
        ret (point_in_square_segment(a) ? *this % a / sqrtl(len2()) : min(sqrtl(vec(a).len2()),
                                                                          sqrtl(vec(a - *this).len2())));
    }

    void turn() {
        swap(x, y);
        x = -x;
    }

    void turn(ld a) {
        *this = vec(x * cosl(a) - y * sinl(a), x * sinl(a) + y * cosl(a));
    }
};

bool segment_in_segment(vec a1, vec a2, vec b1, vec b2) {
    vec a(a2.x - a1.x, a2.y - a1.y), b(a1.x - a2.x, a1.y - a2.y), al(b1.x - a1.x, b1.y - a1.y), ar(b2.x - a1.x,
                                                                                                   b2.y - a1.y), bl(
            b1.x - a2.x, b1.y - a2.y), br(b2.x - a2.x, b2.y - a2.y);
    vec c(b2.x - b1.x, b2.y - b1.y), d(b1.x - b2.x, b1.y - b2.y), cl(a1.x - b1.x, a1.y - b1.y), cr(a2.x - b1.x,
                                                                                                   a2.y - b1.y), dl(
            a1.x - b2.x, a1.y - b2.y), dr(a2.x - b2.x, a2.y - b2.y);
    if ((a % al) * (a % ar) <= 0 && (b % bl) * (b % br) <= 0 && (c % cl) * (c % cr) <= 0 &&
        (d % dl) * (d % dr) <= 0) {
        if (a % al == 0 && a % ar == 0 && (max(a1.x, a2.x) < min(b1.x, b2.x) || max(b1.x, b2.x) < min(a1.x, a2.x) ||
                                           max(a1.y, a2.y) < min(b1.y, b2.y) ||
                                           max(b1.y, b2.y) < min(a1.y, a2.y))) {
            ret 0;
        }
        ret 1;
    } else {
        ret 0;
    }
}

ld dist_from_segment_to_segment(vec a1, vec a2, vec b1, vec b2) {
    ret (segment_in_segment(a1, a2, b1, b2) ? 0.0 : min(abs(vec(a2 - a1).dist_from_point_to_segment(vec(b1 - a1))),
                                                        min(abs(vec(a2 - a1).dist_from_point_to_segment(
                                                                    vec(b2 - a1))),
                                                            min(abs(vec(b2 - b1).dist_from_point_to_segment(
                                                                        a1 - b1)),
                                                                abs(vec(b2 - b1).dist_from_point_to_segment(
                                                                        a2 - b1))))));
}

struct line {
    num a, b, c;

    line() {}

    line(vec x, vec y) {
        a = y.y - x.y;
        b = x.x - y.x;
        c = -a * x.x - b * x.y;
    }

    line(num aa, num bb, vec cc) {
        a = aa;
        b = bb;
        c = -a * cc.x - b * cc.y;
    }

    line(num a, num b, num c) : a(a), b(b), c(c) {}

    friend ostream &operator<<(ostream &out, line &_a) {
        out << _a.a << " " << _a.b << " " << _a.c;
        ret out;
    }

    friend istream &operator>>(istream &in, line &_a) {
        in >> _a.a >> _a.b >> _a.c;
        ret in;
    }

    bool point_in_line(vec aa) {
        ret (a * aa.x + b * aa.y + c == 0);
    }

    num napr(vec aa) {
        if (a * aa.x + b * aa.y + c < 0)ret -1;
        else if (a * aa.x + b * aa.y + c > 0) ret 1;
        else
            ret 0;
    }

    ld dist_from_point_to_line(vec aa) //точка
    {
        ret (a * aa.x + b * aa.y + c) / sqrtl(vec(a, b).len2());
    }

    vec point_of_intersection_of_lines(line aa) {
        if (a != 0)
            ret vec((-b * (aa.c * a - c * aa.a) / (b * aa.a - aa.b * a) - c) / a,
                    (aa.c * a - c * aa.a) / (b * aa.a - aa.b * a));
        else
            ret vec((-aa.b * (c * aa.a - aa.c * a) / (aa.b * a - b * aa.a) - aa.c) / aa.a,
                    (c * aa.a - aa.c * a) / (aa.b * a - b * aa.a));
    }

    bool lines_is_parallel(line aa) {
        if (a == 0) {
            if (aa.a != 0) ret 0;
            ret 1;
        } else {
            if (b == 0) {
                if (aa.b != 0) ret 0;
                ret 1;
            }
            ret abs(aa.a / a - aa.b / b) < eps;
        }
    }

    ld dist_of_parallel_lines(line aa) {
        vec z(a, b);
        ld d = (-c) / sqrtl(z.len2());
        z *= d / sqrtl(z.len2());
        ret aa.dist_from_point_to_line(z);
    }
};

struct circle {
    num r;
    vec t;

    circle() {}

    circle(num x, num y, num r) : t(vec(x, y)), r(r) {}

    bool point_in_circle(vec a) {
        ret sqrtl(vec(a - vec(t.x, t.y)).len2()) <= r;
    }

    friend istream &operator>>(istream &in, circle &a) {
        cin >> a.t.x >> a.t.y >> a.r;
        ret in;
    }

    bool intersection_of_segnent(vec a, vec b) {
        ret vec(b - a).dist_from_point_to_segment(vec(t - a)) < r;
    }

    pair<vec, vec> tangents_from_point(vec a) {
        pair<vec, vec> re;
        num d = rast(t.x, t.y, a.x, a.y);
        ld u = asin(r / d);
        re = {t - a, t - a};
        re.fi.turn(u);
        re.se.turn(-u);
        re.fi /= sqrtl(re.fi.len2());
        re.se /= sqrtl(re.se.len2());
        num d1 = sqrtl(d * d - r * r);
        re.fi *= d1;
        re.se *= d1;
        re.fi += a;
        re.se += a;
        ret re;
    }

    ld ln() {
        ret pi * 2 * r;
    }
};

line bisector_of_three_points(vec x, vec y, vec z) {
    y -= x;
    z -= x;
    vec X = vec(y - z) * (sqrtl(z.len2()) / (sqrtl(z.len2()) + sqrtl(y.len2())));
    X += z;
    X += x;
    ret line(x, X);
}

ll area_of_triangle(vec a, vec b, vec c) {
    ret vec(b - a) % vec(c - a);
}

ll area_of_polygon(vector<vec> &a) {
    ll sum = 0;
    rep(i, 2, sz(a)) {
        sum += area_of_triangle(a[0], a[i - 1], a[i]);
    }
    ret sum;
}

bool point_in_polygon(ll n, vec p, vector<vec> &a) {
    a.pb(a[0]);
    for0(i, n) {
        if (a[i] == p) {
            a.pob();
            ret 1;
        }
    }
    for1(i, n + 1) {
        if (vec(a[i - 1] - a[i]).point_in_segment(p - a[i])) {
            a.pob();
            ret 1;
        }
    }
    ld sum = 0;
    for1(i, n + 1) {
        sum += vec(a[i] - p).angle(a[i - 1] - p);
    }
    a.pob();
    ret (abs(abs(sum) - pi * 2) < eps ? 1 : 0);
}

bool point_in_triangle(vec a, vec b, vec c, vec t) {
    ret abs(area_of_triangle(a, b, c)) ==
        abs(area_of_triangle(a, c, t)) + abs(area_of_triangle(c, b, t)) + abs(area_of_triangle(a, b, t));
}

bool point_in_convex_polygon(ll n, vec p, vector<vec> &a) {
    ll l = 0, r = n;
    p -= a[0];
    if (p.x < 0) ret 0;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        (a[m].polar_angle() <= p.polar_angle() ? l : r) = m;
    }
    if (l == n - 1 || l == 0) ret 0;
    ret point_in_triangle(vec(0, 0), a[l], a[l + 1], p);
}

bool convex_polygon(vector<vec> a) {
    a.pb(a[0]);
    a.pb(a[1]);
    ll n = sz(a);
    bool mi = 0, ma = 0;
    rep(i, 2, n) {
        if (vec(a[i - 1] - a[i - 2]) % vec(a[i] - a[i - 2]) > 0)ma = 1;
        if (vec(a[i - 1] - a[i - 2]) % vec(a[i] - a[i - 2]) < 0)mi = 1;
    }
    ret !(mi && ma);
}

vector<vec> convex_hull(ll n, vector<vec> &a) {
    vec st(10000000000000, 10000000000000);
    for0(i, n) {
        if (a[i].x < st.x || (a[i].x == st.x && a[i].y < st.y)) {
            st = a[i];
        }
    }
    for0(i, n) {
        a[i] -= st;
    }
    sort(all(a), [&](vec &a, vec &b) { ret (a % b == 0 ? a.len2() < b.len2() : a % b > 0); });
    vector<vec> ans;
    for0(i, n) {
        while (sz(ans) > 1 && vec(ans[sz(ans) - 1] - ans[sz(ans) - 2]) % vec(a[i] - ans[sz(ans) - 1]) <= 0) {
            ans.pob();
        }
        ans.pb(a[i]);
    }
    for (auto &x: ans) x += st;
    ret ans;
}

ld area_of_union_of_triangle(vector<vector<vec>> &_a) {
    struct segment {
        vec s, f;
        ll id;

        segment(vec &a, vec &b, ll &id) : s(a), f(b), id(id) {}
    };
    struct item {
        ld y1, y2;
        ll id;

        item() {}

        item(ld y1, ld y2, ll id) : y1(y1), y2(y2), id(id) {}
    };
    ll n = 3 * sz(_a);
    vector<segment> a;
    for0(i, n / 3) {
        for0(j, 3) {
            a.pb({_a[i][j], _a[i][(j + 1) % 3], i});
        }
    }
    vector<ld> b;
    for0(i, n)rep(j, i + 1, n)if (!(line(a[i].s, a[i].f).lines_is_parallel(line(a[j].s, a[j].f)) &&
                                    dist_from_segment_to_segment(a[i].s, a[i].f, a[j].s, a[j].f) < eps) &&
                                  dist_from_segment_to_segment(a[i].s, a[i].f, a[j].s, a[j].f) < eps)
                b.pb(line(a[i].s, a[i].f).point_of_intersection_of_lines(line(a[j].s, a[j].f)).x);
    sort(all(b));
    b.erase(unique(all(b), [&](ld &a, ld &b) { ret abs(a - b) < eps; }), en(b));
    ld re = 0;
    vll used(n / 3, -1);
    vector<item> c(n);
    for0(i, sz(b) - 1) {
        ld x1 = b[i], x2 = b[i + 1];
        ll csz = 0;
        for0(j, n) {
            if (abs(a[j].f.x - a[j].s.x) > eps && min(a[j].s.x, a[j].f.x) <= x1 + eps &&
                max(a[j].f.x, a[j].s.x) >= x2 - eps) {
                c[csz++] = item(line(vec(x1, 0), vec(x1, 1)).point_of_intersection_of_lines(line(a[j].s, a[j].f)).y,
                                line(vec(x2, 0), vec(x2, 1)).point_of_intersection_of_lines(line(a[j].s, a[j].f)).y,
                                a[j].id);
            }
        }
        if (csz % 2) exit(0);
        sort(be(c), be(c) + csz,
             [&](item &a, item &b) { ret a.y1 < b.y1 - eps || abs(a.y1 - b.y1) < eps && a.y2 < b.y2 - eps; });
        ld pl = 0;
        ll cnt = 0;
        item l, r;
        for0(j, csz) {
            if (used[c[j].id] == i) {
                cnt--;
                if (!cnt) {
                    r = c[j];
                    pl += r.y1 - l.y1 + r.y2 - l.y2;
                }
            } else {
                cnt++;
                if (cnt == 1) {
                    l = c[j];
                }
            }
            used[c[j].id] = i;
        }
        re += pl * (x2 - x1) / 2.0;
    }
    ret re;
}

struct pt {
    ld x, y;
    ll c, i;

    pt() {}

    pt(ld x, ld y, ll c) : x(x), y(y), c(c) {}
};

const ll N = 1000;

ll n, s, used[N][N], was[N][N], c[N];
ld dp[N][N][2][2][2][2];
pt p[N];
pair<vec, vec> a[N];

bool check(ll i, ll j) {
    line l1 = line(vec(p[i].x, p[i].y), vec(p[j].x, p[j].y));
    line l;
    vec t;

    l = line(vec(s, s), vec(s, -s));
    t = l.point_of_intersection_of_lines(l1);
    if ((vec(p[i].x, p[i].y) - vec(p[j].x, p[j].y)).point_in_segment(t - vec(p[j].x, p[j].y))) {
        t.x = abs(t.x), t.y = abs(t.y);
        t.x += eps;
        t.y += eps;
        if (min(t.x, t.y) < s) ret 0;
    }

    l = line(vec(s, s), vec(-s, s));
    t = l.point_of_intersection_of_lines(l1);
    if ((vec(p[i].x, p[i].y) - vec(p[j].x, p[j].y)).point_in_segment(t - vec(p[j].x, p[j].y))) {
        t.x = abs(t.x), t.y = abs(t.y);
        t.x += eps;
        t.y += eps;
        if (min(t.x, t.y) < s) ret 0;
    }

    l = line(vec(-s, -s), vec(s, -s));
    t = l.point_of_intersection_of_lines(l1);
    if ((vec(p[i].x, p[i].y) - vec(p[j].x, p[j].y)).point_in_segment(t - vec(p[j].x, p[j].y))) {
        t.x = abs(t.x), t.y = abs(t.y);
        t.x += eps;
        t.y += eps;
        if (min(t.x, t.y) < s) ret 0;
    }

    l = line(vec(-s, -s), vec(-s, s));
    t = l.point_of_intersection_of_lines(l1);
    if ((vec(p[i].x, p[i].y) - vec(p[j].x, p[j].y)).point_in_segment(t - vec(p[j].x, p[j].y))) {
        t.x = abs(t.x), t.y = abs(t.y);
        t.x += eps;
        t.y += eps;
        if (min(t.x, t.y) < s) ret 0;
    }

    ret 1;
}

bool check1(ll i, ll j) {
    if (i == 2 && j == 9) {
        bool fl = 0;
    }
    for0(k, n) {
        if (vec(a[k].fi - a[k].se).point_in_segment(vec(p[i].x, p[i].y) - a[k].se) &&
            vec(a[k].fi - a[k].se).point_in_segment(vec(p[j].x, p[j].y) - a[k].se))
            ret 0;
    }
    ret 1;
}

void solve() {
    cin >> n >> s;
    ll it = 0, id = 0;
    p[it++] = pt(s, s, id++);
    p[it++] = pt(-s, s, id++);
    p[it++] = pt(s, -s, id++);
    p[it++] = pt(-s, -s, id++);
    for0(i, n) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[i] = {vec(x1, y1), vec(x2, y2)};
        p[it++] = pt(x1, y1, id);
        p[it++] = pt(x2, y2, id++);

//        line l1 = line(vec(x1, y1), vec(x2, y2));
//        line l;
//        vec t;
//
//        l = line(vec(s, s), vec(s, -s));
//        t = l.point_of_intersection_of_lines(l1);
//        p[it++] = pt(t.x, t.y, id++);
//
//        l = line(vec(s, s), vec(-s, s));
//        t = l.point_of_intersection_of_lines(l1);
//        p[it++] = pt(t.x, t.y, id++);
//
//        l = line(vec(-s, -s), vec(s, -s));
//        t = l.point_of_intersection_of_lines(l1);
//        p[it++] = pt(t.x, t.y, id++);
//
//        l = line(vec(-s, -s), vec(-s, s));
//        t = l.point_of_intersection_of_lines(l1);
//        p[it++] = pt(t.x, t.y, id++);
    }
    ll sit = it;
    for0(i, sit) {
        for0(j, n) {
            line l1(a[j].fi, a[j].se);
            line l2(vec(p[i].x, p[i].y), vec(p[i].x + l1.a, p[i].y + l1.b));
            vec t = l1.point_of_intersection_of_lines(l2);
            vector<vec> cp{vec(s, s), vec(-s, s), vec(-s, -s), vec(s, -s)};
            if (!point_in_polygon(4, t, cp)) p[it++] = pt(t.x, t.y, id++);
        }
    }
    sort(p, p + it, [&](pt a, pt b) {
        vec va(a.x, a.y), vb(b.x, b.y);
        ret va.polar_angle() < vb.polar_angle();
    });
    for0(i, it) p[i].i = i;
    for0(i, it) {
        for0(j, it) {
            used[i][j] = !check(i, j);
            was[i][j] = check1(i, j);
        }
    }
    for0(i, it) {
        ll tp = -1;
        if (p[i].x <= 0) {
            if (p[i].y <= 0) tp = 0;
            else if (p[i].y >= 0) tp = 1;
        } else if (p[i].x >= s - eps) {
            if (p[i].y <= 0) tp = 2;
            else if (p[i].y >= 0) tp = 3;
        }
        c[i] = tp;
    }
    ld ans = 1e18;
    for0(i, it) {
        for0(j, it) {
            for0(f1, 2) {
                for0(f2, 2) {
                    for0(f3, 2) {
                        for0(f4, 2) {
                            dp[i][j][f1][f2][f3][f4] = 1e18;
                        }
                    }
                }
            }
        }
        dp[i][i][(c[i] == 0)][(c[i] == 1)][(c[i] == 2)][(c[i] == 3)] = 0;
        set<pair<ld, array<ll, 5>>> q;
        q.ins({0, {i, (c[i] == 0), (c[i] == 1), (c[i] == 2), (c[i] == 3)}});
        while (sz(q)) {
            auto [j, f1, f2, f3, f4] = (*be(q)).second;
            q.erase(be(q));
            for0(k, it) {
                if (used[j][k]) con;
                ll g1 = f1 | (c[k] == 0),
                        g2 = f2 | (c[k] == 1),
                        g3 = f3 | (c[k] == 2),
                        g4 = f4 | (c[k] == 3);
                if (dp[i][k][g1][g2][g3][g4] >
                    dp[i][j][f1][f2][f3][f4] +
                    (was[j][k] ? rast(p[j].x, p[j].y, p[k].x, p[k].y) : 0) + eps) {
                    q.erase({dp[i][k][g1][g2][g3][g4], {k, g1, g2, g3, g4}});
                    dp[i][k][g1][g2][g3][g4] = dp[i][j][f1][f2][f3][f4] +
                                               (was[j][k] ? rast(p[j].x, p[j].y, p[k].x, p[k].y) : 0);
                    q.ins({dp[i][k][g1][g2][g3][g4], {k, g1, g2, g3, g4}});
                }
            }
        }
        rep(j, i, it) {
            for1(f1, 2) {
                for1(f2, 2) {
                    for1(f3, 2) {
                        for1(f4, 2) {
                            if (used[j][i]) con;
                            amin(ans, dp[i][j][f1][f2][f3][f4] + (was[j][i] ?
                                                                  rast(p[j].x, p[j].y,
                                                                       p[i].x, p[i].y)
                                                                            : 0));
                        }
                    }
                }
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

fences.cpp: In function 'int main(int, char**)':
fences.cpp:292:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  292 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 33
• Subtask 3: 0 / 49