| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 565059 |
2022-05-20T08:29:37 Z |
maomao90 |
Fences (JOI18_fences) |
C++17 |
|
1 ms |
340 KB |
// 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
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
