Submission #529461

#TimeUsernameProblemLanguageResultExecution timeMemory
5294618e7Fences (JOI18_fences)C++17
18 / 100
1 ms364 KiB
//Challenge: Accepted #include <bits/stdc++.h> using namespace std; #ifdef zisk void debug(){cout << endl;} template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);} template<class T> void pary(T l, T r) { while (l != r) cout << *l << " ", l++; cout << endl; } #else #define debug(...) 0 #define pary(...) 0 #endif #define ll long long #define maxn 420 #define pii pair<double, double> #define eps 1e-9 #define x first #define y second #define io ios_base::sync_with_stdio(0);cin.tie(0); pii vec(pii p, pii q) {return {q.x - p.x, q.y - p.y};} pii operator *(pii p, double x) {return {p.x * x, p.y * x};} pii operator +(pii p, pii q){return {p.x + q.x, p.y + q.y};} double dot(pii p, pii q){return p.x * q.x + p.y * q.y;} double cross(pii p, pii q){return p.x * q.y - p.y * q.x;} int sgn(double x){return (x > eps ? 1 : (x > -eps ? 0 : -1));} bool inl(pii p, pii l1, pii l2) { return abs(cross(vec(p, l1), vec(p, l2))) <= eps && dot(vec(p, l1), vec(p, l2)) <= eps; } bool inter(pii p1, pii p2, pii q1, pii q2) { if (inl(p1, q1, q2) || inl(p2, q1, q2) || inl(q1, p1, p2) || inl(q2, p1, p2)) return 1; if (sgn(cross(vec(p1, q1), vec(p1, q2))) != sgn(cross(vec(p2, q1), vec(p2, q2))) && sgn(cross(vec(q1, p1), vec(q1, p2))) != sgn(cross(vec(q2, p1), vec(q2, p2)))) return 1; return 0; } double sd(pii p, pii q){return (q.x - p.x) * (q.x - p.x) + (q.y - p.y) * (q.y - p.y);} pii getpnt(pii p, pii l1, pii l2) { pii vi = vec(l1, l2); if (sgn(dot(vi, vec(l1, p))) * sgn(dot(vi, vec(l2, p))) != 1) { double len = dot(vec(l1, p), vi) / sd(l1, l2); return l1 + (vi*len); } else { if (sd(p, l1) < sd(p, l2)) return l1; else return l2; } } double dis(pii p, pii l1, pii l2) { return sqrt(sd(p, getpnt(p, l1, l2))); } pii edge[4]; bool valid(pii p, pii q) { bool op[4], oq[4]; int pc = 0, qc = 0; for (int i = 0;i < 4;i++) { op[i] = inl(p, edge[i], edge[(i+1)%4]); oq[i] = inl(q, edge[i], edge[(i+1)%4]); pc += op[i] ? 1 : 0, qc += oq[i] ? 1 : 0; } if (pc && qc) { for (int i = 0;i < 4;i++) { if (op[i] && oq[i]) return 1; } return 0; } else { for (int i = 0;i < 4;i++) { if (inter(p, q, edge[i], edge[(i+1)%4])) { if (!op[i] && !oq[i]) return 0; } } return 1; } } const pii ray0 = {0, 0}, ray1 = {maxn, 1}; pii a[maxn]; const double inf = 1e9; double g[maxn][maxn]; int main() { io int n, s; cin >> n >> s; for (int i = 0;i < n;i++) { cin >> a[2*i].x >> a[2*i].y >> a[2*i+1].x >> a[2*i+1].y; } edge[0] = {s, s}, edge[1] = {s, -s}, edge[2] = {-s, -s}, edge[3] = {-s, s}; /* pii test; cin >> test.x >> test.y; cout << dis(test, a[4], a[5]) << endl; */ int m = 4 * n + 8; for (int i = 0;i < m;i++) { for (int j = 0;j < m;j++) g[i][j] = inf; g[i][i] = 0; } double ans = 8 * s; auto addedge = [&](int i, int j, double d, bool type) { if (type) { debug(i, j, d); g[i*2][j*2+1] = g[j*2+1][i*2] = d; g[i*2+1][j*2] = g[j*2][i*2+1] = d; } else { g[i*2][j*2] = g[j*2][i*2] = d; g[i*2+1][j*2+1] = g[j*2+1][i*2+1] = d; } }; auto change = [&](pii p, pii q) {return inter(p, q, ray0, ray1);}; for (int i = 0;i < 2 * n;i++) { for (int j = i+1;j < 2 * n;j+=2) { if (i % 2 == 0 && j == i+1) { addedge(i, j, 0, change(a[i], a[j])); } else { pii best; if (j % 2) best = getpnt(a[i], a[j], a[j-1]); else best = getpnt(a[i], a[j], a[j+1]); if (valid(a[i], best)) { addedge(i, j, sqrt(sd(best, a[i])), change(a[i], best) ^ change(best, a[j])); } } } if (i % 2 == 0) { for (int j = 0;j < 4;j++) { pii best = getpnt(edge[j], a[i], a[i+1]); if (valid(edge[j], best)) { addedge(2*n+j, i, sqrt(sd(edge[j], best)), change(edge[j], best) ^ change(best, a[i])); } } } } for (int i = 0;i < 4;i++) { addedge(2*n+i, 2*n+(i+1)%4, 2*s, inter(edge[i], edge[(i+1)%4], ray0, ray1)); } for (int k = 0;k < m;k++) { for (int i = 0;i < m;i++) { for (int j = 0;j < m;j++) { g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } } for (int i = 0;i < m;i+=2) { ans = min(ans, g[i][i+1]); } /* int qu, qv; while (cin >> qu >> qv) { debug("same: ", g[qu*2][qv*2]); debug("dif: ", g[qu*2][qv*2+1]); } */ cout << fixed << setprecision(10) << ans << endl; }

Compilation message (stderr)

fences.cpp: In lambda function:
fences.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fences.cpp:109:4: note: in expansion of macro 'debug'
  109 |    debug(i, j, d);
      |    ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...