Submission #565059

#	Time	Username	Problem	Language	Result	Execution time	Memory
565059		maomao90	Fences (JOI18_fences)	C++17	0 / 100	1 ms	340 KiB

fences

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 115;
const ld EPS = 1e-9;

int n, s;
ld g[MAXN][MAXN];

struct Point {
    ld x, y;
    ld getd(const Point &o) const {
        return sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y));
    }
    bool operator==(const Point &o) const {
        return abs(x - o.x) < EPS && abs(y - o.y) < EPS;
    }
    Point& operator+=(const Point &o) {
        x += o.x; y += o.y;
        return *this;
    }
    Point operator-() const {
        return Point{-x, -y};
    }
    Point& operator-=(const Point &o) {
        (*this) += (-o);
        return *this;
    }
    Point operator+(const Point &o) const {
        Point res = *this;
        res += o;
        return res;
    }
    Point operator-(const Point &o) const {
        Point res = *this;
        res -= o;
        return res;
    }
    friend ostream& operator<<(ostream &os, const Point &o) {
        return os << o.x << ' ' << o.y;
    }
    friend istream& operator>>(istream &is, Point &o) {
        return is >> o.x >> o.y;
    }
} flags[4];

struct Line {
    // ax + by = c
    ld a, b, c;
    Line() {}
    Line(Point x, Point y) {
        if (abs(x.x - y.x) < EPS) {
            a = 1;
            b = 0;
            c = x.x;
        } else {
            Point d = y - x;
            ld m = (ld) d.y / d.x;
            a = -m;
            b = 1;
            c = a * x.x + b * x.y;
        }
    }
    Point isect(const Line &o) const {
        // ax + by = c
        // o.ax + o.by = o.c
        // a * o.a * x + b * o.a * y = c * o.a
        // o.a * a * x + o.b * a * y = o.c * a
        ld y;
        if (abs(b * o.a - o.b * a) < EPS) {
            y = INF;
        } else {
            y = (c * o.a - o.c * a) / (b * o.a - o.b * a);
        }
        ld x = (c - b * y) / a;
        return Point{x, y};
    }
    Point eval(ld x) {
        if (b == 0) {
            return Point{0, 0};
        }
        ld y = (c - a * x) / b;
        return Point{x, y};
    }
};

struct LineSegment {
    Point a, b;
    Line l;
    LineSegment() {}
    LineSegment(Point _a, Point _b): a(_a), b(_b), l(_a, _b) {
        if (a.x > b.x) {
            swap(a, b);
        }
    }
    bool isect(const LineSegment &o) {
        if (a.x == b.x && o.a.x == o.b.x) {
            return 0;
        }
        if (a.y == b.y && o.a.y == o.b.y) {
            return 0;
        }
        if (a == o.a || a == o.b || b == o.a || b == o.b) {
            return 0;
        }
        Point p = l.isect(o.l);
        return a.x + EPS < p.x && p.x < b.x - EPS;
    }
    Point eval(ld x) {
        Point p = l.eval(x);
        if (p.x < a.x || p.y < a.y || p.x > b.x || p.y > b.y) {
            return Point{0, 0};
        }
        return p;
    }
} ban[4], sgs[MAXN];

ld getsp(LineSegment ls, Point p) {
    Point is = {-1, -1};
    if (abs(ls.a.x - ls.b.x) < EPS) { // vertical line
        is = {ls.a.x, p.y};
    } else if (abs(ls.a.y - ls.b.y) < EPS) {
        is = {p.x, ls.a.y};
    } else {
        Point d = ls.b - ls.a;
        ld m = (ld) d.y / d.x;
        ld im = -1 / m;
        Line ol(p, Point{p.x + 1, p.y + im});
        is = ls.l.isect(ol);
    }
    if (is.x < ls.a.x || is.y < ls.a.y) {
        is = ls.a;
    } else if (is.x > ls.b.x || is.y > ls.b.y) {
        is = ls.b;
    }
    LineSegment ols(p, is);
    bool pos = 1;
    int j = -1;
    REP (i, 0, 4) {
        if (is == flags[i]) {
            swap(is, p);
        }
        if (p == flags[i]) {
            j = i;
        }
        if (ols.isect(ban[i])) {
            pos = 0;
            break;
        }
    }
    if (j != -1) {
        if (is.x > -s && is.y < s && j == 0) {
           pos = 0;
        } else if (is.x < s && is.y < s && j == 1) {
            pos = 0;
        } else if (is.x < s && is.y > -s && j == 2) {
            pos = 0;
        } else if (is.x > -s && is.y > -s && j == 3) {
            pos = 0;
        }
    }
    if (pos) {
        return is.getd(p);
    } else {
        return INF;
    }
}
ld getsp(const LineSegment &t, const LineSegment &o) {
    return min({getsp(t, o.a), getsp(t, o.b), getsp(o, t.a), getsp(o, t.b)});
}

inline int getType(Point p) {
    if (p.x <= -s && p.y >= s) {
        return 0;
    } else if (p.x >= s && p.y >= s) {
        return 1;
    } else if (p.x >= s && p.y <= -s) {
        return 2;
    } else if (p.x <= -s && p.y <= -s) {
        return 3;
    }
    return -1;
}

inline int getType(LineSegment l) {
    int res = 0, t;
    t = getType(l.a);
    if (t != -1) {
        res |= 1 << t;
    }
    t = getType(l.b);
    if (t != -1) {
        res |= 1 << t;
    }
    t = getType(l.eval(s));
    if (t != -1) {
        res |= 1 << t;
    }
    t = getType(l.eval(-s));
    if (t != -1) {
        res |= 1 << t;
    }
    return res;
}

ld dist[MAXN][1 << 4];
int vis[MAXN][1 << 4];
ld dijkstra(int src) {
    REP (i, 0, n) {
        REP (j, 0, 1 << 4) {
            dist[i][j] = INF;
            vis[i][j] = 0;
        }
    }
    dist[src][getType(sgs[src])] = 0;
    REP (z, 0, n * (1 << 4)) {
        ld d = INF;
        int u = -1, msk;
        REP (i, 0, n) {
            REP (j, 0, 1 << 4) {
                if (vis[i][j]) continue;
                if (mnto(d, dist[i][j])) {
                    u = i;
                    msk = j;
                }
            }
        }
        if (u == -1) {
            break;
        }
        cerr << u << ' ' << msk << '\n';
        vis[u][msk] = 1;
        REP (i, 0, n) {
            int nmsk = msk | getType(sgs[i]);
            mnto(dist[i][nmsk], d + g[u][i]);
        }
    }
    return dist[src][(1 << 4) - 1];
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cout << setprecision(10);
    cin >> n >> s;
    flags[0] = {-s, s}, flags[1] = {s, s},
        flags[2] = {s, -s}, flags[3] = {-s, -s};
    REP (i, 0, 4) {
        ban[i] = LineSegment(flags[i], flags[(i + 1) % 4]);
        sgs[n + i] = LineSegment(flags[i], flags[i]);
    }
    REP (i, 0, n) {
        Point a, b;
        cin >> a >> b;
        sgs[i] = LineSegment(a, b);
    }
    n += 4;
    REP (i, 0, n) {
        g[i][i] = 0;
        REP (j, i + 1, n) {
            g[i][j] = g[j][i] = getsp(sgs[i], sgs[j]);
            cerr << i << ' ' << j << ' ' << g[i][j] << '\n';
        }
    }
    ld ans = INF;
    REP (i, 0, n) {
        mnto(ans, dijkstra(i));
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:278:17: warning: narrowing conversion of '- s' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  278 |     flags[0] = {-s, s}, flags[1] = {s, s},
      |                 ^~
fences.cpp:278:21: warning: narrowing conversion of 's' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  278 |     flags[0] = {-s, s}, flags[1] = {s, s},
      |                     ^
fences.cpp:278:37: warning: narrowing conversion of 's' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  278 |     flags[0] = {-s, s}, flags[1] = {s, s},
      |                                     ^
fences.cpp:278:40: warning: narrowing conversion of 's' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  278 |     flags[0] = {-s, s}, flags[1] = {s, s},
      |                                        ^
fences.cpp:279:21: warning: narrowing conversion of 's' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  279 |         flags[2] = {s, -s}, flags[3] = {-s, -s};
      |                     ^
fences.cpp:279:24: warning: narrowing conversion of '- s' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  279 |         flags[2] = {s, -s}, flags[3] = {-s, -s};
      |                        ^~
fences.cpp:279:41: warning: narrowing conversion of '- s' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  279 |         flags[2] = {s, -s}, flags[3] = {-s, -s};
      |                                         ^~
fences.cpp:279:45: warning: narrowing conversion of '- s' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  279 |         flags[2] = {s, -s}, flags[3] = {-s, -s};
      |                                             ^~
fences.cpp: In function 'ld dijkstra(int)':
fences.cpp:265:44: warning: 'msk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  265 |             int nmsk = msk | getType(sgs[i]);
      |                                            ^

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