제출 #565059

#제출 시각아이디문제언어결과실행 시간메모리
565059maomao90Fences (JOI18_fences)C++17
0 / 100
1 ms340 KiB
// 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; }

컴파일 시 표준 에러 (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]);
      |                                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...