Submission #892817

#	Time	Username	Problem	Language	Result	Execution time	Memory
892817		box	Fences (JOI18_fences)	C++17	100 / 100	12 ms	1060 KiB

fences

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using T = double;

const T eps = 1e-7;

struct point { T x, y; };
point operator+(const point a, const point b) { return {a.x + b.x, a.y + b.y}; }
point operator-(const point a, const point b) { return {a.x - b.x, a.y - b.y}; }
point operator*(const point a, const T v) { return {a.x * v, a.y * v}; }
T dot(const point a, const point b) { return a.x * b.x + a.y * b.y; }
T len(const point a) { return sqrt(a.x * a.x + a.y * a.y); }
T cross(const point a, const point b) { return a.x * b.y - a.y * b.x; }
bool cw(const point a, const point b, const point c) { return cross(b - a, c - a) > 0; }
bool ccw(const point a, const point b, const point c) { return cross(b - a, c - a) < 0; }

struct line { point a, b; };
bool isect(line p, line q, bool touch) {
    for (int rep = 0; rep < 2; rep++) {
        bool f = 0;
        f |= cw(p.a, p.b, q.a) && ccw(p.a, p.b, q.b);
        f |= ccw(p.a, p.b, q.a) && cw(p.a, p.b, q.b);
        if (touch) {
            f |= cw(p.a, p.b, q.a) && !cw(p.a, p.b, q.b);
            f |= !cw(p.a, p.b, q.a) && cw(p.a, p.b, q.b);
        }
        if (!f) return 0;
        swap(p, q);
    }
    return 1;
}
point proj(const line p, const point a) {
    point v = p.b - p.a, u = a - p.a;
    T ratio = dot(u, v) / dot(v, v);
    if (ratio < 0 || ratio > 1 || dot(v, v) == 0)
        return len(p.a - a) < len(p.b - a) ? p.a : p.b;
    return p.a + v * ratio;
}

const line half{point{T(0), T(0)}, point{T(1), T{401}}};

int n, s;
vector<line> lines;
line diag1, diag2;

bool good(const line l) {
    return !isect(l, diag1, 0) && !isect(l, diag2, 0);
}

void ckmin(T &a, T b) {
    a = min(a, b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    lines.resize(n);
    for (auto &[p, q] : lines) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        p = point{T(a), T(b)};
        q = point{T(c), T(d)};
    }
    diag1 = line{point{T(-s), T(-s)}, point{T(s), T(s)}};
    diag2 = line{point{T(s), T(-s)}, point{T(-s), T(s)}};
    for (int x : {-s, s}) for (int y : {-s, s}) {
        point p{T(x), T(y)};
        lines.push_back({p, p});
    }
    vector<line> tmp;
    for (line l : lines) {
        if (!isect(l, half, 1)) tmp.push_back(l);
        else {
            point v = l.b - l.a;
            T low = 0, hi = 1;
            for (int it = 0; it < 35; it++) {
                T m = (low + hi) / 2;
                isect(line{l.a, l.a + v * m}, half, 1) ? hi = m : low = m;
            }
            T m = (low + hi) / 2;
            tmp.push_back(line{l.a, l.a + v * (m - eps)});
            tmp.push_back(line{l.a + v * (m + eps), l.b});
        }
    }
    swap(tmp, lines);
    n = sz(lines);
    const T inf = s * 8;
    vector dist(n * 2, vector<T>(n * 2, inf));
    for (int i = 0; i < sz(lines); i++) {
        for (int j = i + 1; j < sz(lines); j++) {
            auto add = [&](const line l) {
                if (good(l)) {
                    T d = len(l.b - l.a);
                    bool t = isect(l, half, 1);
                    if (t) {
                        ckmin(dist[i][j + n], d);
                        ckmin(dist[i + n][j], d);
                        ckmin(dist[j][i + n], d);
                        ckmin(dist[j + n][i], d);
                    } else {
                        ckmin(dist[i][j], d);
                        ckmin(dist[i + n][j + n], d);
                        ckmin(dist[j + n][i + n], d);
                        ckmin(dist[j][i], d);
                    }
                }
            };
            add(line{lines[i].a, lines[j].a});
            add(line{lines[i].a, lines[j].b});
            add(line{lines[i].b, lines[j].a});
            add(line{lines[i].b, lines[j].b});
            add(line{lines[i].a, proj(lines[j], lines[i].a)});
            add(line{lines[i].b, proj(lines[j], lines[i].b)});
            add(line{lines[j].a, proj(lines[i], lines[j].a)});
            add(line{lines[j].b, proj(lines[i], lines[j].b)});
        }
    }
    for (int k = 0; k < n * 2; k++) for (int i = 0; i < n * 2; i++) for (int j = 0; j < n * 2; j++)
        ckmin(dist[i][j], dist[i][k] + dist[k][j]);
    T ans = inf;
    for (int i = 0; i < n; i++) ckmin(ans, dist[i][i + n]);
    cout << fixed << setprecision(8) << ans << '\n';
}

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